{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Paint House III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #粉刷房子 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个小城市里，有 <code>m</code> 个房子排成一排，你需要给每个房子涂上 <code>n</code> 种颜色之一（颜色编号为 <code>1</code> 到 <code>n</code> ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。</p>\n",
    "\n",
    "<p>我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 <code>houses = [1,2,2,3,3,2,1,1]</code> ，它包含 5 个街区 <code> [{1}, {2,2}, {3,3}, {2}, {1,1}]</code> 。）</p>\n",
    "\n",
    "<p>给你一个数组 <code>houses</code> ，一个 <code>m * n</code> 的矩阵 <code>cost</code> 和一个整数 <code>target</code> ，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>houses[i]</code>：是第 <code>i</code> 个房子的颜色，<strong>0</strong> 表示这个房子还没有被涂色。</li>\n",
    "\t<li><code>cost[i][j]</code>：是将第 <code>i</code> 个房子涂成颜色 <code>j+1</code> 的花费。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 <code>target</code> 个街区。如果没有可用的涂色方案，请返回 <strong>-1</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>房子涂色方案为 [1,2,2,1,1]\n",
    "此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。\n",
    "涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]\n",
    "此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。\n",
    "给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == houses.length == cost.length</code></li>\n",
    "\t<li><code>n == cost[i].length</code></li>\n",
    "\t<li><code>1 <= m <= 100</code></li>\n",
    "\t<li><code>1 <= n <= 20</code></li>\n",
    "\t<li><code>1 <= target <= m</code></li>\n",
    "\t<li><code>0 <= houses[i] <= n</code></li>\n",
    "\t<li><code>1 <= cost[i][j] <= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [paint-house-iii](https://leetcode.cn/problems/paint-house-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [paint-house-iii](https://leetcode.cn/problems/paint-house-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0,0,0,0]\\n[[1,10],[10,1],[10,1],[1,10],[5,1]]\\n5\\n2\\n3', '[0,2,1,2,0]\\n[[1,10],[10,1],[10,1],[1,10],[5,1]]\\n5\\n2\\n3', '[3,1,2,3]\\n[[1,1,1],[1,1,1],[1,1,1],[1,1,1]]\\n4\\n3\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        adjList = defaultdict(list)\n",
    "        for h1, h2, cost in pipes:\n",
    "            adjList[h1].append((cost, h2))\n",
    "            adjList[h2].append((cost, h1))\n",
    "        for i in range(n):\n",
    "            adjList[0].append((wells[i], i+1))\n",
    "        heap = [(0, 0)]\n",
    "        visited = set()\n",
    "        total = 0\n",
    "        while heap:\n",
    "            cost, house = heapq.heappop(heap)\n",
    "            if house not in visited:\n",
    "                visited.add(house)\n",
    "                total += cost\n",
    "                for cost, n_house in adjList[house]:\n",
    "                    if n_house not in visited:\n",
    "                        heapq.heappush(heap, (cost, n_house))\n",
    "            if len(visited) == n + 1:\n",
    "                break\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1. at least one house has well built inside house\n",
    "    2. all housed not need to be connected to get water supplied\n",
    "    3. the cost of building a well in current group is smaller than connecting current group to a already supplied group\n",
    "    '''\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        id = [i for i in range(n)] # the root of house is itself at the beginning\n",
    "        cost = [wells[i] for i in range(n)] # the cost of building well in current group\n",
    "        edges_cost = 0\n",
    "\n",
    "        pipes = sorted(pipes, key=lambda x: x[-1])  # Sort by the last element of each sublist\n",
    "\n",
    "\n",
    "        for h1, h2, c in pipes:\n",
    "            p = self.find_root(id, h1 - 1)\n",
    "            q = self.find_root(id, h2 - 1)\n",
    "            if p == q:\n",
    "                continue \n",
    "            cur_combine_cost = c + min(cost[p], cost[q])\n",
    "            cur_individual_cost = cost[p] + cost[q]\n",
    "            if cur_combine_cost <= cur_individual_cost:\n",
    "                id[p] = q\n",
    "                cost[q] = min(cost[q], cost[p])\n",
    "                edges_cost += c\n",
    "\n",
    "            # if  c > cost[h2-1] and c >  cost[h1-1]:\n",
    "            #     continue # the cost of building h1/h2 and connect to h1/h2 costs more than them build themselves\n",
    "            # # connect the lowest cost path\n",
    "            # if c <= cost[h2-1] and cost[h1-1] < cost[h2-1]: # h1 build wells\n",
    "            #     p = self.find_root(id, h1 - 1)\n",
    "            #     q = self.find_root(id, h2 - 1)\n",
    "            #     id[q] = p \n",
    "            #     cost[h2-1] = c \n",
    "            \n",
    "            # elif c <= cost[h1-1] and cost[h2-1] < cost[h1-1]: # h2 build wells\n",
    "            #     p = self.find_root(id, h2 - 1)\n",
    "            #     q = self.find_root(id, h1 - 1)\n",
    "            #     id[q] = p \n",
    "            #     cost[h1-1] = c        \n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n):\n",
    "            if i == id[i]:\n",
    "                res += cost[i]\n",
    "\n",
    "        return res+edges_cost\n",
    "\n",
    "    def find_root(self, id, i):\n",
    "        while i != id[i]:\n",
    "            id[i] = id[id[i]]\n",
    "            i = id[i]\n",
    "        return i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data = [i for i in range(n)]\n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        else:\n",
    "            self.data[x] = self.find(self.data[x])\n",
    "            return self.data[x] \n",
    "    def un(self, x, y):\n",
    "        fx,fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] = fx \n",
    "            return True \n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        edges = [(wells[i], 0, i+1) for i in range(n)]\n",
    "        for a, b, w in pipes:\n",
    "            edges.append((w, a, b))\n",
    "        edges.sort() \n",
    "        dsu = DSU(n+1) \n",
    "        ans = 0 \n",
    "        #print(edges)\n",
    "        for w, a, b in edges:\n",
    "            if dsu.un(a, b):\n",
    "                ans += w\n",
    "        #print(dsu.data) \n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        num_node = len(wells)\n",
    "        edges = []\n",
    "        for i in range(len(wells)):\n",
    "            edges.append([0,i+1,wells[i]])\n",
    "        \n",
    "        \n",
    "        edges.extend(pipes)\n",
    "        \n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        fathers = [x for x in range(num_node+1)]\n",
    "\n",
    "        def find(ele):\n",
    "            if ele == fathers[ele]:\n",
    "                return ele\n",
    "\n",
    "            fathers[ele] = find(fathers[ele])\n",
    "            return fathers[ele]\n",
    "\n",
    "        used_edges = []\n",
    "        ans = 0\n",
    "        for i,j,cost in edges:\n",
    "            father_i = find(i)\n",
    "            father_j = find(j)\n",
    "            if father_i != father_j:\n",
    "                used_edges.append(cost)\n",
    "                fathers[father_i] = min(father_i,father_j)\n",
    "                fathers[father_j] = min(father_i,father_j)\n",
    "                ans+=cost\n",
    "            \n",
    "            if len(used_edges) == num_node:\n",
    "                break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        self.parent = list(range(n+1))\n",
    "        self.cot = n+1\n",
    "        res = 0\n",
    "        # regard well as a node 0, being a water source\n",
    "        for i in range(n):\n",
    "            pipes.append([0,i+1,wells[i]])\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        idx_p = 0\n",
    "        while not self.cot==1:\n",
    "            cur = pipes[idx_p]\n",
    "            if not self.find(cur[0])==self.find(cur[1]):\n",
    "                self.union(cur[0], cur[1])\n",
    "                res += cur[2]\n",
    "            idx_p += 1\n",
    "        return res\n",
    "\n",
    "    def find(self, x):\n",
    "        while not x==self.parent[x]:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            return\n",
    "        self.parent[rootX] = rootY\n",
    "        self.cot -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, n):\n",
    "        while n != self.parent[n]:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if self.rank[p1] > self.rank[p2]:\n",
    "            self.parent[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "        else:\n",
    "            self.parent[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        for v in range(1, n + 1):\n",
    "            pipes.append([0, v, wells[v - 1]])\n",
    "        \n",
    "        pipes.sort(key = lambda x: x[2])\n",
    "        uf, res, edge = UF(n + 1), 0, 0\n",
    "        for u, v, c in pipes:\n",
    "            if uf.find(u) != uf.find(v):\n",
    "                uf.union(u, v)\n",
    "                edge += 1\n",
    "                res += c\n",
    "            if edge == n:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        self.parent = list(range(n+1))\n",
    "        self.cot = n+1\n",
    "        res = 0\n",
    "        # regard well as a node 0, being a water source\n",
    "        for i in range(n):\n",
    "            pipes.append([0,i+1,wells[i]])\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        idx_p = 0\n",
    "        while not self.cot==1:\n",
    "            cur = pipes[idx_p]\n",
    "            if self.union(cur[0], cur[1]):\n",
    "                res += cur[2]\n",
    "            idx_p += 1\n",
    "        return res\n",
    "\n",
    "    def find(self, x):\n",
    "        while not x==self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            return False\n",
    "        self.parent[rootX] = rootY\n",
    "        self.cot -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        self.pa = list(range(n + 1))\n",
    "\n",
    "        for i, x in enumerate(wells):\n",
    "            pipes.append((0, i + 1, x))\n",
    "        pipes.sort(key = lambda x: x[2])\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for u, v, cost in pipes:\n",
    "            u, v = self.find(u), self.find(v)\n",
    "            if u != v:\n",
    "                self.pa[u] = v\n",
    "                ans += cost\n",
    "                cnt += 1\n",
    "            if cnt == n:\n",
    "                return ans\n",
    "        return -1\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS():                  #并查集类\n",
    "  def __init__(self,n):\n",
    "    self.n=n\n",
    "    self.parent=[0]*self.n                   #并查集存储结构\n",
    "    self.rnk=[-1]*self.n                    #存储结点的秩(近似于高度)\n",
    "  def Init(self):                               #并查集初始化\n",
    "    for i in range(0,self.n):\n",
    "      self.parent[i]=i\n",
    "      self.rnk[i]=0\n",
    "  def Find(self,x):         #递归算法：并查集中查找x结点的根结点\n",
    "    if x!=self.parent[x]:\n",
    "      self.parent[x]=self.Find(self.parent[x])        #路径压缩\n",
    "    return self.parent[x]\n",
    "  def Union(self,rx,ry):                        #并查集中x和y的两个集合的合并\n",
    "    if self.rnk[rx]<self.rnk[ry]:\n",
    "      self.parent[rx]=ry                 #rx结点作为ry的孩子\n",
    "    else:\n",
    "      if self.rnk[rx]==self.rnk[ry]:          #秩相同，合并后rx的秩增1\n",
    "        self.rnk[rx]+=1\n",
    "      self.parent[ry]=rx                  #ry结点作为rx的孩子\n",
    "\n",
    "class Solution:\n",
    "  def minCostToSupplyWater(self, n:int,wells:List[int],pipes:List[List[int]])->int:\n",
    "    for i in range(1,n+1):     #建立超级源点0\n",
    "      pipes.append([0,i,wells[i-1]])\n",
    "    return self.Kruskal(n+1,pipes)\n",
    "  def Kruskal(self,n,E):         #Kruskal算法\n",
    "    ufs=UFS(n) \n",
    "    E.sort(key=itemgetter(2))           #按边权值递增排序\n",
    "    ans=0\n",
    "    ufs.Init()                    #初始化并查集\n",
    "    k,j=0,0                           #k表示当前构造生成树的边数\n",
    "    while k<n-1:                        #生成的边数小于n-1时循环\n",
    "      u1,v1=E[j][0],E[j][1]               #取一条边(u1,v1)\n",
    "      sn1,sn2=ufs.Find(u1),ufs.Find(v1)   #两个顶点所属的集合编号\n",
    "      if sn1!=sn2:                        #添加该边不会构成回路\n",
    "        ans+=E[j][2]      #产生最小生成树的一条边\n",
    "        k+=1                #生成边数增1\n",
    "        ufs.Union(sn1,sn2)        #将sn1和sn2两个顶点合并\n",
    "      j+=1                #遍历下一条边\n",
    "    return ans\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.sz = [1] * n\n",
    "        self.n_comp = n\n",
    "    def find(self,x):\n",
    "        if x!=self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x] < self.sz[y]:\n",
    "            y,x = x,y\n",
    "        self.fa[y] = x\n",
    "        self.sz[x] + self.sz[y]\n",
    "        self.n_comp -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        uf = UF(n+1)\n",
    "        for i,x in enumerate(wells):\n",
    "            pipes.append([0,i+1,x])\n",
    "\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        \n",
    "        ans = 0\n",
    "        for x,y,w in pipes:\n",
    "            if  uf.union(x,y):\n",
    "               ans += w \n",
    "\n",
    "            if uf.n_comp == 1:\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        self.parent = list(range(n+1))\n",
    "        self.cot = n+1\n",
    "        res = 0\n",
    "        # regard well as a node 0, being a water source\n",
    "        for i in range(n):\n",
    "            pipes.append([0,i+1,wells[i]])\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        idx_p = 0\n",
    "        while not self.cot==1:\n",
    "            cur = pipes[idx_p]\n",
    "            if self.union(cur[0], cur[1]):\n",
    "                res += cur[2]\n",
    "            idx_p += 1\n",
    "        return res\n",
    "\n",
    "    def find(self, x):\n",
    "        while not x==self.parent[x]:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            return False\n",
    "        self.parent[rootX] = rootY\n",
    "        self.cot -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        for i in range(n):\n",
    "            pipes.append([i+1,0,wells[i]])\n",
    "        ans = 0\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        father = [_ for _ in range(n+1)]\n",
    "        def find(x):\n",
    "            if father[x] == x:\n",
    "                return x\n",
    "            father[x] = find(father[x])\n",
    "            return father[x]\n",
    "        \n",
    "        def join(x,y):\n",
    "            father[find(x)] = find(y)\n",
    "        \n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            while find(pipes[index][0]) == find(pipes[index][1]):\n",
    "                index += 1\n",
    "            join(pipes[index][0], pipes[index][1])\n",
    "            ans += pipes[index][2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        uf =UnionFind(n+1)\n",
    "        for i in range(n):\n",
    "            pipes.append([0, i+1, wells[i]])\n",
    "        \n",
    "        pipes.sort(key=lambda it: it[2])\n",
    "        ans = 0\n",
    "        for i, j, w in pipes:\n",
    "            if uf.union(i, j):\n",
    "                ans += w\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        root = list(range(n + 1))\n",
    "        def Find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = Find(root[x])\n",
    "            return root[x]\n",
    "        def Union(x,y):\n",
    "            root[x] = y\n",
    "\n",
    "        for idx,well in enumerate(wells):\n",
    "            pipes.append([idx + 1,0,well])\n",
    "        pipes.sort(key = lambda x : x[-1])\n",
    "        print(pipes)\n",
    "        min_cost = 0\n",
    "        cnt = 0\n",
    "        for x,y,c in pipes:\n",
    "            rx,ry = Find(x),Find(y)\n",
    "            if rx != ry:\n",
    "                Union(rx,ry)\n",
    "                min_cost += c\n",
    "        return min_cost\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        p={i:i for i in range(n+1)}\n",
    "        for i,v in enumerate(wells):\n",
    "            pipes.append([0,i+1,v])\n",
    "\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "        cnt=0\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        for s,e,c in pipes:\n",
    "            a=find(s)\n",
    "            b=find(e)\n",
    "            if a!=b:\n",
    "                union(s,e)\n",
    "                cnt+=c\n",
    "        return cnt \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        # 增加虚拟节点\n",
    "        # 新的边为对应节点建筑水井的代价\n",
    "        # 构建最小生成树\n",
    "        # 不知道几棵树-->想办法连接成为一棵树-->增加虚拟节点\n",
    "        Tree=[i for i in range(n+2)]\n",
    "        def find_root(idx):\n",
    "            if idx==Tree[idx]:\n",
    "                return idx\n",
    "            while idx!=Tree[idx]:\n",
    "                Tree[idx]=Tree[Tree[idx]]\n",
    "                idx=Tree[idx]\n",
    "            return idx\n",
    "        for i in range(len(wells)):\n",
    "            pipes.append([i+1, n+1, wells[i]])\n",
    "        pipes.sort(key=lambda x:x[2])\n",
    "        val=0\n",
    "        for pipe in pipes:\n",
    "            root_a=find_root(pipe[0])\n",
    "            root_b=find_root(pipe[1])\n",
    "            if root_a!=root_b:\n",
    "                Tree[root_a]=root_b\n",
    "                val+=pipe[2]\n",
    "        return val\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        for index, w in enumerate(wells):\n",
    "            n_index = index+1\n",
    "            edges.append([0, n_index, w])\n",
    "        \n",
    "        pipes_cost = {}\n",
    "        for p in pipes:\n",
    "            s, t, v = p\n",
    "            if (s, t) not in pipes_cost:\n",
    "                pipes_cost[(s, t)] = v\n",
    "            else:\n",
    "                pipes_cost[(s, t)] = min(pipes_cost[(s, t)], v)\n",
    "        \n",
    "        for p, cost in pipes_cost.items():\n",
    "            edges.append([p[0], p[1], cost])\n",
    "        \n",
    "        edges.sort(key=lambda x:x[2])\n",
    "\n",
    "        parent = [i for i in range(n+1)]\n",
    "        def find(i):\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "        \n",
    "        def union(i, j):\n",
    "            irep, jrep = find(i), find(j)\n",
    "            if irep == jrep:\n",
    "                return\n",
    "            else:\n",
    "                parent[irep] = jrep\n",
    "        \n",
    "        total_cost = 0\n",
    "        for e in edges:\n",
    "            s, t, v = e\n",
    "            if find(s) != find(t):\n",
    "                union(s, t)\n",
    "                total_cost += v\n",
    "\n",
    "            if len(set(parent)) == 1:\n",
    "                break\n",
    "        \n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        # 邻接表表示的双向图\n",
    "       graph = defaultdict(list)\n",
    "\n",
    "       # 添加索引为0的虚拟顶点。\n",
    "       # 然后在每一栋房子上加一条边，按成本加权\n",
    "       for index, cost in enumerate(wells):\n",
    "           graph[0].append((cost, index + 1))\n",
    "\n",
    "       # 将双向边添加到图中\n",
    "       for house_1, house_2, cost in pipes:\n",
    "           graph[house_1].append((cost, house_2))\n",
    "           graph[house_2].append((cost, house_1))\n",
    "\n",
    "       # 用于维护已添加到的所有顶点的集合\n",
    "       # 最终的 MST(最小生成树)从顶点 0 开始。\n",
    "       mst_set = set([0])\n",
    "\n",
    "       # 堆维护要访问的边的顺序，\n",
    "       # 从起源于顶点0的边开始。\n",
    "       # 注意：我们能够从任意节点开始。\n",
    "       heapq.heapify(graph[0])\n",
    "       edges_heap = graph[0]\n",
    "\n",
    "       total_cost = 0\n",
    "       while len(mst_set) < n + 1:\n",
    "           cost, next_house = heapq.heappop(edges_heap)\n",
    "           if next_house not in mst_set:\n",
    "               # 将新顶点添加到集合中\n",
    "               mst_set.add(next_house)\n",
    "               total_cost += cost\n",
    "               # 在下一轮扩大候选边的选择范围\n",
    "               for new_cost, neighbor_house in graph[next_house]:\n",
    "                   if neighbor_house not in mst_set:\n",
    "                       heapq.heappush(edges_heap, (new_cost, neighbor_house))\n",
    "\n",
    "       return total_cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for index, cost in enumerate(wells):\n",
    "            graph[0].append((cost, index+1))\n",
    "            # graph[index+1].append((cost, 0))\n",
    "        for house_1,house_2,cost in pipes:\n",
    "            graph[house_1].append((cost, house_2))\n",
    "            graph[house_2].append((cost, house_1))\n",
    "        mst_set = set([0])\n",
    "        heapq.heapify(graph[0])\n",
    "        edges_heap = graph[0]\n",
    "\n",
    "        total_cost = 0\n",
    "        while len(mst_set)<n+1:\n",
    "            cost, next_house = heapq.heappop(edges_heap)\n",
    "            if next_house not in mst_set:\n",
    "                mst_set.add(next_house)\n",
    "                total_cost += cost\n",
    "                for new_cost,neighbor_house in graph[next_house]:\n",
    "                    if neighbor_house not in mst_set:\n",
    "                        heapq.heappush(edges_heap, (new_cost,neighbor_house))\n",
    "                        \n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for index, cost in enumerate(wells):\n",
    "            graph[0].append((cost, index+1))\n",
    "            # graph[index+1].append((cost, 0))\n",
    "        for house_1,house_2,cost in pipes:\n",
    "            graph[house_1].append((cost, house_2))\n",
    "            graph[house_2].append((cost, house_1))\n",
    "        mst_set = set([0])\n",
    "        heapq.heapify(graph[0])\n",
    "        edges_heap = graph[0]\n",
    "\n",
    "        res = 0\n",
    "        while len(mst_set)<n+1:\n",
    "            cost, nextN = heapq.heappop(edges_heap)\n",
    "            if nextN not in mst_set:\n",
    "                res += cost\n",
    "                mst_set.add(nextN)\n",
    "                for c,neighbor in graph[nextN]:\n",
    "                    if neighbor not in mst_set:\n",
    "                        heapq.heappush(edges_heap, (c,neighbor))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "\n",
    "       # 邻接表表示的双向图\n",
    "       graph = defaultdict(list)\n",
    "\n",
    "       # 添加索引为0的虚拟顶点。\n",
    "       # 然后在每一栋房子上加一条边，按成本加权\n",
    "       for index, cost in enumerate(wells):\n",
    "           graph[0].append((cost, index + 1))\n",
    "\n",
    "       # 将双向边添加到图中\n",
    "       for house_1, house_2, cost in pipes:\n",
    "           graph[house_1].append((cost, house_2))\n",
    "           graph[house_2].append((cost, house_1))\n",
    "\n",
    "       # 用于维护已添加到的所有顶点的集合\n",
    "       # 最终的 MST(最小生成树)从顶点 0 开始。\n",
    "       mst_set = set([0])\n",
    "\n",
    "       # 堆维护要访问的边的顺序，\n",
    "       # 从起源于顶点0的边开始。\n",
    "       # 注意：我们能够从任意节点开始。\n",
    "       heapq.heapify(graph[0])\n",
    "       edges_heap = graph[0]\n",
    "\n",
    "       total_cost = 0\n",
    "       while len(mst_set) < n + 1:\n",
    "           cost, next_house = heapq.heappop(edges_heap)\n",
    "           if next_house not in mst_set:\n",
    "               # 将新顶点添加到集合中\n",
    "               mst_set.add(next_house)\n",
    "               total_cost += cost\n",
    "               # 在下一轮扩大候选边的选择范围\n",
    "               for new_cost, neighbor_house in graph[next_house]:\n",
    "                   if neighbor_house not in mst_set:\n",
    "                       heapq.heappush(edges_heap, (new_cost, neighbor_house))\n",
    "\n",
    "       return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "\n",
    "       # 邻接表表示的双向图\n",
    "       graph = defaultdict(list)\n",
    "\n",
    "       # 添加索引为0的虚拟顶点。\n",
    "       # 然后在每一栋房子上加一条边，按成本加权\n",
    "       for index, cost in enumerate(wells):\n",
    "           graph[0].append((cost, index + 1))\n",
    "\n",
    "       # 将双向边添加到图中\n",
    "       for house_1, house_2, cost in pipes:\n",
    "           graph[house_1].append((cost, house_2))\n",
    "           graph[house_2].append((cost, house_1))\n",
    "\n",
    "       # 用于维护已添加到的所有顶点的集合\n",
    "       # 最终的 MST(最小生成树)从顶点 0 开始。\n",
    "       mst_set = set([0])\n",
    "\n",
    "       # 堆维护要访问的边的顺序，\n",
    "       # 从起源于顶点0的边开始。\n",
    "       # 注意：我们能够从任意节点开始。\n",
    "       heapq.heapify(graph[0])\n",
    "       edges_heap = graph[0]\n",
    "\n",
    "       total_cost = 0\n",
    "       while len(mst_set) < n + 1:\n",
    "           cost, next_house = heapq.heappop(edges_heap)\n",
    "           if next_house not in mst_set:\n",
    "               # 将新顶点添加到集合中\n",
    "               mst_set.add(next_house)\n",
    "               total_cost += cost\n",
    "               # 在下一轮扩大候选边的选择范围\n",
    "               for new_cost, neighbor_house in graph[next_house]:\n",
    "                   if neighbor_house not in mst_set:\n",
    "                       heapq.heappush(edges_heap, (new_cost, neighbor_house))\n",
    "\n",
    "       return total_cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for index, cost in enumerate(wells):\n",
    "            graph[0].append((cost, index+1))\n",
    "            # graph[index+1].append((cost, 0))\n",
    "        for house_1,house_2,cost in pipes:\n",
    "            graph[house_1].append((cost, house_2))\n",
    "            graph[house_2].append((cost, house_1))\n",
    "        mst_set = set([0])\n",
    "\n",
    "        edges_heap = graph[0]\n",
    "        heapq.heapify(edges_heap)\n",
    "\n",
    "        res = 0\n",
    "        while len(mst_set)<n+1:\n",
    "            cost, nextN = heapq.heappop(edges_heap)\n",
    "            if nextN not in mst_set:\n",
    "                res += cost\n",
    "                mst_set.add(nextN)\n",
    "                for c,neighbor in graph[nextN]:\n",
    "                    if neighbor not in mst_set:\n",
    "                        heapq.heappush(edges_heap, (c,neighbor))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for index, cost in enumerate(wells):\n",
    "            graph[0].append((cost, index+1))\n",
    "            # graph[index+1].append((cost, 0))\n",
    "        for house_1,house_2,cost in pipes:\n",
    "            graph[house_1].append((cost, house_2))\n",
    "            graph[house_2].append((cost, house_1))\n",
    "        mst_set = set([0])\n",
    "\n",
    "        edges_heap = graph[0]\n",
    "        heapq.heapify(edges_heap)\n",
    "\n",
    "        res = 0\n",
    "        while len(mst_set)<n+1:\n",
    "            cost, nextN = heapq.heappop(edges_heap)\n",
    "            if nextN not in mst_set:\n",
    "                res += cost\n",
    "                mst_set.add(nextN)\n",
    "                for c,neighbor in graph[nextN]:\n",
    "                    if neighbor not in mst_set:\n",
    "                        heapq.heappush(edges_heap, (c,neighbor))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "\n",
    "       # 邻接表表示的双向图\n",
    "       graph = defaultdict(list)\n",
    "\n",
    "       # 添加索引为0的虚拟顶点。\n",
    "       # 然后在每一栋房子上加一条边，按成本加权\n",
    "       for index, cost in enumerate(wells):\n",
    "           graph[0].append((cost, index + 1))\n",
    "\n",
    "       # 将双向边添加到图中\n",
    "       for house_1, house_2, cost in pipes:\n",
    "           graph[house_1].append((cost, house_2))\n",
    "           graph[house_2].append((cost, house_1))\n",
    "\n",
    "       # 用于维护已添加到的所有顶点的集合\n",
    "       # 最终的 MST(最小生成树)从顶点 0 开始。\n",
    "       mst_set = set([0])\n",
    "\n",
    "       # 堆维护要访问的边的顺序，\n",
    "       # 从起源于顶点0的边开始。\n",
    "       # 注意：我们能够从任意节点开始。\n",
    "       heapq.heapify(graph[0])\n",
    "       edges_heap = graph[0]\n",
    "\n",
    "       total_cost = 0\n",
    "       while len(mst_set) < n + 1:\n",
    "           cost, next_house = heapq.heappop(edges_heap)\n",
    "           if next_house not in mst_set:\n",
    "               # 将新顶点添加到集合中\n",
    "               mst_set.add(next_house)\n",
    "               total_cost += cost\n",
    "               # 在下一轮扩大候选边的选择范围\n",
    "               for new_cost, neighbor_house in graph[next_house]:\n",
    "                   if neighbor_house not in mst_set:\n",
    "                       heapq.heappush(edges_heap, (new_cost, neighbor_house))\n",
    "\n",
    "       return total_cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        ref = defaultdict(list)\n",
    "        for i, j, k in pipes:\n",
    "            ref[i].append((k, j))\n",
    "            ref[j].append((k, i))\n",
    "        heaq = []\n",
    "        for i in range(n):\n",
    "            heappush(heaq, (wells[i], i + 1))\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        while heaq:\n",
    "            cost, node = heappop(heaq)\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "            res += cost\n",
    "            for c, n in ref[node]:\n",
    "                if n not in visited:\n",
    "                    heappush(heaq, (c, n))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        #解题思路：\n",
    "        #一个房子，要么连接水管，要么铺管道，不知道如何处理\n",
    "        #技巧：在图中添加一个虚拟顶点0，0与各边相连，其权值为水井的成本\n",
    "\n",
    "        edges = [[] for i in range(n + 1)]\n",
    "        for a,b,cost in pipes:\n",
    "            edges[a].append((cost,b))\n",
    "            edges[b].append((cost,a))\n",
    "        for i,cost in enumerate(wells):\n",
    "            edges[0].append((cost,i + 1))\n",
    "\n",
    "        visited = set()\n",
    "        out_edges = [(0,0)] #从顶点0开始\n",
    "        res = 0\n",
    "        while out_edges and len(visited) != (n + 1):\n",
    "            cost,city = heapq.heappop(out_edges)\n",
    "            if city not in visited:\n",
    "                visited.add(city)\n",
    "                res += cost\n",
    "                for next_cost,next_city in edges[city]:\n",
    "                    heapq.heappush(out_edges,(next_cost,next_city))\n",
    "        return res if len(visited) == (n + 1) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        #解题思路：\n",
    "        #一个房子，要么连接水管，要么铺管道，不知道如何处理\n",
    "        #技巧：在图中添加一个虚拟顶点0，0与各边相连，其权值为水井的成本\n",
    "\n",
    "        edges = [[] for i in range(n + 1)]\n",
    "        for a,b,cost in pipes:\n",
    "            edges[a].append((cost,b))\n",
    "            edges[b].append((cost,a))\n",
    "        for i,cost in enumerate(wells):\n",
    "            edges[0].append((cost,i + 1))\n",
    "\n",
    "        visited = set()\n",
    "        out_edges = [(0,0)] #从顶点0开始\n",
    "        res = 0\n",
    "        while out_edges and len(visited) != (n + 1):\n",
    "            cost,city = heapq.heappop(out_edges)\n",
    "            if city not in visited:\n",
    "                visited.add(city)\n",
    "                res += cost\n",
    "                for next_cost,next_city in edges[city]:\n",
    "                    heapq.heappush(out_edges,(next_cost,next_city))\n",
    "        return res if len(visited) == (n + 1) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        edges = [[] for _ in range(n + 1)]\n",
    "        for a, b, cost in pipes:\n",
    "            edges[a].append((b, cost))\n",
    "            edges[b].append((a, cost))\n",
    "        for i, v in enumerate(wells):\n",
    "            edges[0].append((i + 1, v))\n",
    "        \n",
    "        \n",
    "        tree = []\n",
    "        vis = [False] * (n + 1)\n",
    "        h = [(0, 0)]\n",
    "        arr = [i for i in range(n + 1)]\n",
    "        res = 0\n",
    "        while h:\n",
    "            cost, p = heapq.heappop(h)\n",
    "            \n",
    "            if not vis[p]:\n",
    "                vis[p] = True\n",
    "                tree.append(p)\n",
    "                res += cost\n",
    "                \n",
    "                for next_pos, next_cost in edges[p]:\n",
    "                    if not vis[next_pos]:\n",
    "                        heapq.heappush(h, (next_cost, next_pos))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        edges = [[] for _ in range(n + 1)]\n",
    "        for a, b, cost in pipes:\n",
    "            edges[a].append((b, cost))\n",
    "            edges[b].append((a, cost))\n",
    "        for i, v in enumerate(wells):\n",
    "            edges[0].append((i + 1, v))\n",
    "        \n",
    "        \n",
    "        tree = []\n",
    "        vis = [False] * (n + 1)\n",
    "        h = [(0, 0)]\n",
    "        arr = [i for i in range(n + 1)]\n",
    "        res = 0\n",
    "        while h:\n",
    "            cost, p = heapq.heappop(h)\n",
    "            \n",
    "            if not vis[p]:\n",
    "                vis[p] = True\n",
    "                tree.append(p)\n",
    "                res += cost\n",
    "                \n",
    "                for next_pos, next_cost in edges[p]:\n",
    "                    if not vis[next_pos]:\n",
    "                        heapq.heappush(h, (next_cost, next_pos))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param wells:\n",
    "        :param pipes:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        anslist = SortedList(key=lambda x: x[0])\n",
    "        idxmap = {}\n",
    "        for i in range(n):\n",
    "            anslist.add((wells[i], i))\n",
    "            idxmap[i] = wells[i]\n",
    "        ret = []\n",
    "        m1 = defaultdict(list)\n",
    "        for i in pipes:\n",
    "            m1[i[0]-1].append((i[1]-1, i[2]))\n",
    "            m1[i[1]-1].append((i[0]-1, i[2]))\n",
    "        processed = set()\n",
    "        while anslist:\n",
    "            val, idx = anslist.pop(0)\n",
    "            ret.append((val, idx))\n",
    "            processed.add(idx)\n",
    "            for i in m1.get(idx, []):\n",
    "                newxx = i[1]\n",
    "                if i[0] in processed:\n",
    "                    continue\n",
    "                if newxx < idxmap[i[0]]:\n",
    "\n",
    "                    anslist.remove((idxmap[i[0]], i[0]))\n",
    "                    idxmap[i[0]] = newxx\n",
    "                    anslist.add((newxx, i[0]))\n",
    "        return sum([i[0] for i in ret])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param wells:\n",
    "        :param pipes:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        anslist = SortedList(key=lambda x: x[0])\n",
    "        idxmap = {}\n",
    "        for i in range(n):\n",
    "            anslist.add((wells[i], i))\n",
    "            idxmap[i] = wells[i]\n",
    "        ret = []\n",
    "        m1 = defaultdict(list)\n",
    "        for i in pipes:\n",
    "            m1[i[0]-1].append((i[1]-1, i[2]))\n",
    "            m1[i[1]-1].append((i[0]-1, i[2]))\n",
    "        processed = set()\n",
    "        while anslist:\n",
    "            val, idx = anslist.pop(0)\n",
    "            ret.append((val, idx))\n",
    "            processed.add(idx)\n",
    "            for i in m1.get(idx, []):\n",
    "                newxx = i[1]\n",
    "                if i[0] in processed:\n",
    "                    continue\n",
    "                if newxx < idxmap[i[0]]:\n",
    "                    anslist.remove((idxmap[i[0]], i[0]))\n",
    "                    idxmap[i[0]] = newxx\n",
    "                    anslist.add((newxx, i[0]))\n",
    "        return sum([i[0] for i in ret])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToSupplyWater(self, n:int,wells:List[int],pipes:List[List[int]])->int:\n",
    "        if n==1:return wells[n-1]\n",
    "        adj=[[] for _ in range(n+1)] \n",
    "        for e in pipes:\n",
    "          a,b,w=e[0],e[1],e[2]\n",
    "          adj[a].append([b,w])\n",
    "          adj[b].append([a,w])\n",
    "        for i in range(1,n+1):      #建立超级源点0\n",
    "            adj[0].append([i,wells[i-1]])\n",
    "            adj[i].append([0,wells[i-1]])\n",
    "        U=[False for _ in range(n+1)]\n",
    "        ans=0          #存放答案\n",
    "        k=0        #累计选择的边数\n",
    "        pqu=[]          #小根堆，结点类型为[w,vno]\n",
    "        U[0]=True\n",
    "        for e in adj[0]:heapq.heappush(pqu,[e[1],e[0]])\n",
    "        while pqu:\n",
    "            [w,v]=heapq.heappop(pqu)       \t\t\t#出队\n",
    "            if U[v]==False:\n",
    "                U[v]=True\n",
    "                ans+=w\n",
    "                k+=1\n",
    "                if k==n:return ans\n",
    "                for e in adj[v]:heapq.heappush(pqu,[e[1],e[0]])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            \n",
    "            # Find the colors with the minimum and second to minimum\n",
    "            # in the previous row.\n",
    "            min_color = second_min_color = None\n",
    "            for color in range(k):\n",
    "                cost = costs[i - 1][color]\n",
    "                if min_color is None or cost < costs[i - 1][min_color]:\n",
    "                    second_min_color = min_color\n",
    "                    min_color = color\n",
    "                elif second_min_color is None or cost < costs[i - 1][second_min_color]:\n",
    "                    second_min_color = color\n",
    "            for j in range(k): \n",
    "                if j == min_color:\n",
    "                    costs[i][j] += costs[i-1][second_min_color]\n",
    "                else:\n",
    "                    costs[i][j] += costs[i-1][min_color]\n",
    "        \n",
    "        return min(costs[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# O(N*C) N rooms count C color count\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        room_len = len(costs)\n",
    "        if not room_len:\n",
    "            return 0\n",
    "        color_len = len(costs[0])\n",
    "        if not color_len:\n",
    "            return 0\n",
    "        # state dp[0~n-1][0~2] dp[i][j] 第i个房间涂j颜色的花费最小值\n",
    "        dp = [[0 for _ in range(color_len)] for _ in range(room_len)]\n",
    "        # init\n",
    "        for idx in range(color_len):\n",
    "            dp[0][idx] = costs[0][idx]\n",
    "        # tranfer: dp[i][j] = min(dp[i-1][:j or j+1:] + costs[i][j])\n",
    "        for r_idx in range(1, room_len):\n",
    "            for c_idx in range(color_len):\n",
    "                pre_min_costs = [dp[r_idx - 1][pre_c_idx] for pre_c_idx in\n",
    "                                 range(color_len) if pre_c_idx != c_idx]\n",
    "                dp[r_idx][c_idx] = min(pre_min_costs) + costs[r_idx][c_idx]\n",
    "        # print(costs)\n",
    "        # print(dp)\n",
    "        # result\n",
    "        return min([dp[room_len-1][c_idx] for c_idx in range(color_len)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs: return 0\n",
    "        l, k = len(costs), len(costs[0])\n",
    "        for i in range(1, l):\n",
    "            for j in range(k):\n",
    "                tmp = costs[i-1][:]\n",
    "                tmp.pop(j)\n",
    "                costs[i][j] += min(tmp)\n",
    "        return min(costs[:][-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        costs_length = len(costs)\n",
    "        if costs_length == 0:\n",
    "            return 0\n",
    "\n",
    "        cost_matrix = [[0] * len(costs[0]) for i in range(costs_length)]\n",
    "        cost_matrix[0] = costs[0][:]\n",
    "\n",
    "        for i in range(1, costs_length):\n",
    "            houses = costs[i]\n",
    "            for j in range(len(houses)):\n",
    "                lst = cost_matrix[i-1][:]\n",
    "                del lst[j]\n",
    "                cost_matrix[i][j] = houses[j] + min(lst)\n",
    "\n",
    "        return min(cost_matrix[len(cost_matrix)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # n houses, can be painted with one of the k colors\n",
    "        # cost of each color is different.\n",
    "        # no two adjacent houses have the same color.\n",
    "        # Time complexity: O(NK)\n",
    "        # Space complexity: O(K)\n",
    "        \n",
    "        if costs == []: return 0\n",
    "        row, col = len(costs), len(costs[0])\n",
    "        \n",
    "        dp = costs[0][:]\n",
    "        for i in range(1, row):\n",
    "            firVal, secVal = float('inf'), float('inf')\n",
    "            for j in range(col):\n",
    "                if dp[j] < firVal:\n",
    "                    firVal, secVal = dp[j], firVal\n",
    "                elif dp[j] < secVal:\n",
    "                    secVal = dp[j]\n",
    "            for j in range(col):\n",
    "                if dp[j] != firVal: dp[j] = costs[i][j] + firVal\n",
    "                else: dp[j] = costs[i][j] +  secVal\n",
    "        return min(dp)\n",
    "\t\t\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if len(costs) == 0: return 0\n",
    "        dp = [[0 for _ in range(len(costs[0]))] for _ in range(len(costs))]\n",
    "        # dp[i][k] = min(dp[i-1][{r,g,b}-k])+costs[i][k]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, len(costs)):\n",
    "            for k in range(len(costs[i])):\n",
    "                l = list(range(len(costs[i])))\n",
    "                l.remove(k)\n",
    "                temp = dp[i-1][l[0]]\n",
    "                for j in range(1, len(l)):\n",
    "                    temp = min(dp[i-1][l[j]], temp)\n",
    "                dp[i][k] = temp + costs[i][k]\n",
    "        # print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        if not n:\n",
    "            return 0\n",
    "        m = len(costs[0])\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                val = float('inf')\n",
    "                for k in range(m):\n",
    "                    if k == j:\n",
    "                        continue\n",
    "                    val = min(val, costs[i-1][k])\n",
    "                costs[i][j] += val\n",
    "        \n",
    "        return min(costs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs:\n",
    "            return 0\n",
    "        n=len(costs)\n",
    "        k=len(costs[0])\n",
    "        if k==0:\n",
    "            return 0\n",
    "        dp=[[0]*k for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for c in range(k):\n",
    "                if i==0:\n",
    "                    dp[0][c]=costs[0][c]\n",
    "                    continue\n",
    "                dp[i][c]=min(dp[i-1][co] for co in range(k) if co!=c)+costs[i][c]\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs or not costs[0]:\n",
    "            return 0\n",
    "\n",
    "        s1, s2 = len(costs), len(costs[0])  # s1=房子数量，s2=颜色数量\n",
    "\n",
    "        dp = [[0] * s2 for _ in range(s1)]\n",
    "        for i2 in range(s2):\n",
    "            dp[0][i2] = costs[0][i2]\n",
    "\n",
    "        for i1 in range(1, s1):\n",
    "            for i2 in range(s2):\n",
    "                dp[i1][i2] = costs[i1][i2] + min(dp[i1 - 1][ii2] for ii2 in range(s2) if ii2 != i2)\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        if not costs:\n",
    "            return 0\n",
    "        n, k = len(costs), len(costs[0])\n",
    "        @lru_cache\n",
    "        def dfs(index: int, pre: int) -> int:\n",
    "            if index == n:\n",
    "                return 0\n",
    "            ret = float('inf')\n",
    "            for i in range(k):\n",
    "                if i == pre: continue\n",
    "                ret = min(ret, costs[index][i] + dfs(index + 1, i))\n",
    "            return ret    \n",
    "        return dfs(0, -1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        if n == 0: return 0\n",
    "        k = len(costs[0])\n",
    "        # dp = [[0]*k for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(k):\n",
    "                flag = 1\n",
    "                temp = costs[i][j]\n",
    "                for m in range(k):\n",
    "                    if j != m:\n",
    "                        if flag:\n",
    "                            costs[i][j] += costs[i-1][m]\n",
    "                            flag = 0\n",
    "                        else:\n",
    "                            costs[i][j] = min(costs[i][j],costs[i-1][m] + temp)\n",
    "        # print(costs)\n",
    "        return min(costs[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        m, n = len(costs), len(costs[0])\n",
    "\n",
    "        dp = costs[0]\n",
    "\n",
    "        for i in range(1, len(costs)):\n",
    "            first, second = None, None\n",
    "            for n in dp:\n",
    "                if first is None:\n",
    "                    first = n\n",
    "                    continue\n",
    "                if n <= first:\n",
    "                    second = first\n",
    "                    first = n\n",
    "                elif second is None or n < second:\n",
    "                    second = n\n",
    "\n",
    "            for j in range(len(dp)):\n",
    "                if dp[j] == first:\n",
    "                    dp[j] = second + costs[i][j]\n",
    "                else:\n",
    "                    dp[j] = first + costs[i][j]\n",
    "            \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "        dp = [[100*21]*k for _ in range(n)]\n",
    "\n",
    "        dp[0] = costs[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(k):\n",
    "                for z in range(k):\n",
    "                    if j == z:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][z]+costs[i][j])\n",
    "        \n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        colors = len(costs[0])\n",
    "        dp = [[0] * colors for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for k in range(colors):\n",
    "                dp[i][k] = min(dp[i-1][:k]+dp[i-1][k+1:]) + costs[i-1][k]\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # dp[i][j]表示从0-i号房子被粉刷且i号房子被粉刷成颜色j的最小花费\n",
    "        n_h = len(costs)\n",
    "        n_c = len(costs[0])\n",
    "        dp = [[0 for i in range(n_c)] for j in range(n_h)]\n",
    "        \n",
    "        for h in range(n_h):\n",
    "            print(dp)\n",
    "            for c in range(n_c):\n",
    "                if h == 0:\n",
    "                    dp[h][c] = copy.deepcopy(costs[h][c])\n",
    "                    \n",
    "                else:\n",
    "                    mincol = 1e9\n",
    "                    for j in range(n_c):\n",
    "                        if j != c:\n",
    "                            mincol = min(mincol, copy.deepcopy(dp[h-1][j]))\n",
    "                            # print(h-1, c,j, dp, mincol)\n",
    "                    dp[h][c] = mincol + copy.deepcopy(costs[h][c])\n",
    "                    # print(h,c,mincol, dp[h][c], costs[h][c])\n",
    "        # print(dp)\n",
    "        res = 1e9\n",
    "        for c in range(n_c):\n",
    "            res = min(res, dp[n_h-1][c])\n",
    "        return res\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "\n",
    "        dp = dict()\n",
    "        return self.func(costs, 0, -1, dp)\n",
    "\n",
    "    def func(self, costs, pos, color, dp):\n",
    "        if (pos, color) in dp:\n",
    "            return dp[(pos, color)]\n",
    "        n = len(costs)\n",
    "        k = len(costs[0])\n",
    "\n",
    "        if pos >= len(costs):\n",
    "            res = 0\n",
    "        else:\n",
    "            min_color = -1\n",
    "            min_cost = -1\n",
    "            for ncolor in range(k):\n",
    "                if ncolor != color:\n",
    "                    ncost = costs[pos][ncolor] + self.func(costs, pos+1, ncolor, dp)\n",
    "                    if min_cost < 0 or min_cost > ncost:\n",
    "                        min_color = ncolor\n",
    "                        min_cost = ncost\n",
    "            res = min_cost\n",
    "        dp[(pos, color)] = res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # 房子颜色\n",
    "        m, n = len(costs), len(costs[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, m):\n",
    "            min_2 = self.min_2(dp[i - 1])\n",
    "            for k in range(n):\n",
    "                dp[i][k] = costs[i][k] + (min_2[0][0] if k != min_2[0][1] else min_2[1][0])\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "    def min_2(self, l):\n",
    "        s = SortedList()\n",
    "        for i, val in enumerate(l):\n",
    "            s.add((val, i))\n",
    "            if len(s) == 3:\n",
    "                s.pop()\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        # min1, min2 = 0, 0\n",
    "        # ind = 0\n",
    "        # kinds = len(costs[0])\n",
    "        # for cost in costs:\n",
    "        #     for i in range(kinds):\n",
    "        #         if i != ind:\n",
    "        #             cost[i] += min1   \n",
    "        #         else: \n",
    "        #             cost[i] += min2\n",
    "        #     min1 = min(cost)\n",
    "        #     ind = cost.index(min1)\n",
    "        #     min2 = min(cost[:ind] + cost[ind + 1:])\n",
    "\n",
    "        # return min1\n",
    "\n",
    "        min1, min2, ind = 0, 0, 0\n",
    "        for cost in costs:\n",
    "            m1, m2, ind_ = inf, inf, 0\n",
    "            for i, new in enumerate(cost):\n",
    "                total = new + min1 if i != ind else new + min2\n",
    "                if total < m1:\n",
    "                    m1, m2, ind_ = total, m1, i\n",
    "                elif total < m2:\n",
    "                    m2 = total\n",
    "            min1, min2, ind = m1, m2, ind_\n",
    "        return min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n, m = len(costs), len(costs[0])\n",
    "        dp = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        # 记录dp[i-1][j]的最小值和次小值\n",
    "        min_1, min_2 = 0, 0\n",
    "        for i in range(n):\n",
    "            tmp_1, tmp_2 = inf, inf\n",
    "            for j in range(m):\n",
    "                if i:\n",
    "                    if dp[i - 1][j] == min_1:\n",
    "                        dp[i][j] = min_2\n",
    "                    else:\n",
    "                        dp[i][j] = min_1\n",
    "                dp[i][j] += costs[i][j]\n",
    "                if dp[i][j] < tmp_1:\n",
    "                    tmp_2 = tmp_1\n",
    "                    tmp_1 = dp[i][j]\n",
    "                elif dp[i][j] < tmp_2:\n",
    "                    tmp_2 = dp[i][j]\n",
    "            min_1, min_2 = tmp_1, tmp_2\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n, m = len(costs), len(costs[0])\n",
    "        dp = [[inf for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            dp[0][i] = costs[0][i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][k])\n",
    "                dp[i][j] += costs[i][j]\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in costs[0]] for _ in costs]\n",
    "        dp[0] = costs[0]\n",
    "        for idx in range(1, len(costs)):\n",
    "            for i in range(len(costs[0])):\n",
    "                tmp = 10**9\n",
    "                for j in range(len(costs[0])):\n",
    "                    if i != j:\n",
    "                        print(i, j)\n",
    "                        tmp = min(tmp, dp[idx-1][j] + costs[idx][i])\n",
    "                dp[idx][i] = tmp\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j,c in enumerate(costs[i]):\n",
    "                if j != pre:\n",
    "                    ans = min(ans,dfs(i+1,j)+c)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostII(self, costs: List[List[int]]) -> int:\n",
    "        return self.answer_1(costs)\n",
    "\n",
    "    def answer_1(self, costs):\n",
    "        n = len(costs)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        k = len(costs[0])\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def _memo_resolve(house_index, color):\n",
    "            if house_index == n - 1:\n",
    "                return costs[house_index][color]\n",
    "\n",
    "            tmp_cost = float(\"inf\")\n",
    "\n",
    "            for next_color in range(k):\n",
    "                if next_color == color:\n",
    "                    continue\n",
    "\n",
    "                tmp_cost = min(tmp_cost, _memo_resolve(house_index + 1, next_color))\n",
    "            return costs[house_index][color] + tmp_cost\n",
    "\n",
    "        cost = float(\"inf\")\n",
    "\n",
    "        for index in range(k):\n",
    "            cost = min(cost, _memo_resolve(0, index))\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        for i in range(m):\n",
    "            if houses[i]:\n",
    "                for j in range(n):\n",
    "                    cost[i][j] = float(\"inf\")\n",
    "                cost[i][houses[i] - 1] = 0\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dp(i, color, nb):\n",
    "            if nb > i + 1 or nb == 0:\n",
    "                return float(\"inf\")\n",
    "            if i == 0:\n",
    "                return cost[i][color - 1]\n",
    "\n",
    "            same = dp(i - 1, color, nb) \n",
    "            diff = min(dp(i - 1, j, nb - 1) for j in range(1, n + 1) if j != color)\n",
    "            return min(same, diff) + cost[i][color - 1]\n",
    "\n",
    "        ans = min(dp(m - 1, color, target) for color in range(1, n + 1))\n",
    "        return ans if ans < float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            dp[i_] = [[1e6+1]*n for j in range(target)]\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i__,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_two_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_one_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i_][t][j] = dp[i__][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = dp[i__][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i_][0][min_idx] = dp[i__][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp)\n",
    "                    dp[i_][0][j] = dp[i__][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i_][t][j] = dp[i__][t][j]\n",
    "                        else:\n",
    "                            dp[i_][t][j] = dp[i__][t-1][min_idx]\n",
    "                    dp[i_][0][min_idx] = dp[i__][0][min_idx]\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            dp[i_][min_t-1:max_t] = [[1e6+1]*n for j in range(max_t-min_t+1)]\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i__,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_two_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_one_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i_][t][j] = dp[i__][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = dp[i__][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i_][0][min_idx] = dp[i__][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp)\n",
    "                    dp[i_][0][j] = dp[i__][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i_][t][j] = dp[i__][t][j]\n",
    "                        else:\n",
    "                            dp[i_][t][j] = dp[i__][t-1][min_idx]\n",
    "                    if j == min_idx:\n",
    "                        dp[i_][0][min_idx] = dp[i__][0][min_idx]\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            tmp = dp[i-1][t-1]\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i-1,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_two_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_one_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i][t][j] = dp[i-1][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = dp[i-1][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i][0][min_idx] = dp[i-1][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp)\n",
    "                    dp[i][0][j] = dp[i-1][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = dp[i-1][t][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = dp[i-1][t-1][min_idx]\n",
    "                    if j == min_idx:\n",
    "                        dp[i][0][min_idx] = dp[i-1][0][min_idx]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        #n color\n",
    "        #m houses.len\n",
    "        #dp\n",
    "        if n == 1 and target > 1:\n",
    "            return -1\n",
    "        if m < target:\n",
    "            return -1\n",
    "        houses = [x - 1 for x in houses]\n",
    "        # print(houses)\n",
    "        dp = [[-1] * (n) for _ in range(target + 1)]\n",
    "        if houses[0] == -1:\n",
    "            for i in range(n):\n",
    "                dp[1][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[1][houses[0]] = 0\n",
    "\n",
    "        for i in range(1, m):\n",
    "            # print(dp)\n",
    "            ndp = [[-1] * (n) for _ in range(target + 1)]\n",
    "            mg = min(target, i + 1)\n",
    "            if houses[i] == -1:\n",
    "                for c in range(n):\n",
    "                    # ndp[cg][c]=min(dp[cg][c],dp[cg-1][notc])\n",
    "                    for g in range(mg + 1):\n",
    "                        ops = -1\n",
    "                        if dp[g][c] != -1:\n",
    "                            ops = dp[g][c] + cost[i][c]\n",
    "                        if g - 1 > 0:\n",
    "                            for prec in range(n):\n",
    "                                if prec != c and dp[g - 1][prec] != -1:\n",
    "                                    if ops == -1:\n",
    "                                        ops = dp[g - 1][prec] + cost[i][c]\n",
    "                                    else:\n",
    "                                        if dp[g - 1][prec] + cost[i][c] < ops:\n",
    "                                            ops = dp[g - 1][prec] + cost[i][c]\n",
    "                        ndp[g][c] = ops\n",
    "                        # if houses[i]!=-1:\n",
    "            else:\n",
    "                # all c\n",
    "                for g in range(1, mg + 1):\n",
    "                    c = houses[i]\n",
    "                    if dp[g][c] != -1:\n",
    "                        ndp[g][c] = dp[g][c]\n",
    "                    if g > 1:\n",
    "                        for other in range(n):\n",
    "                            if other!=c and dp[g - 1][other] != -1:\n",
    "                                    if ndp[g][c] == -1:\n",
    "                                        ndp[g][c] = dp[g - 1][other]\n",
    "                                    else:\n",
    "                                        if dp[g - 1][other] < ndp[g][c]:\n",
    "                                            ndp[g][c] = dp[g - 1][other]\n",
    "\n",
    "            dp = ndp\n",
    "        ans=-1\n",
    "        for x in dp[target]:\n",
    "            if x!=-1:\n",
    "                if ans==-1:\n",
    "                    ans=x\n",
    "                else:\n",
    "                    if x<ans:\n",
    "                        ans=x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[inf] * (target + 1) for _ in range(n + 1)]\n",
    "        if houses[0] != 0:\n",
    "            dp[houses[0]][1] = 0\n",
    "        else:\n",
    "            for j in range(1,n + 1):\n",
    "                dp[j][1] = cost[0][j - 1]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            color = houses[i]\n",
    "            tmp = dp.copy()\n",
    "            dp = [[inf] * (target + 1) for _ in range(n + 1)]\n",
    "            if color == 0:\n",
    "                for j1 in range(1,n + 1):\n",
    "                    for k in range(1,target + 1):\n",
    "                        for j2 in range(1,n + 1):\n",
    "                            if j1 == j2: \n",
    "                                dp[j1][k] = min(dp[j1][k],tmp[j2][k] + cost[i][j1-1])\n",
    "                            else:\n",
    "                                dp[j1][k] = min(dp[j1][k],tmp[j2][k-1] + cost[i][j1-1])\n",
    "            else:\n",
    "                for k in range(1,target + 1):\n",
    "                    for j2 in range(1, n + 1):\n",
    "                        if j2 == color:\n",
    "                            dp[color][k] = min(dp[color][k],tmp[j2][k])\n",
    "                        else:\n",
    "                            dp[color][k] = min(dp[color][k],tmp[j2][k-1])\n",
    "\n",
    "        ans = min(dp[j][target] for j in range(1,n + 1))\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[inf] * (target + 1) for _ in range(n + 1)]\n",
    "        if houses[0] != 0:\n",
    "            dp[houses[0]][1] = 0\n",
    "        else:\n",
    "            for j in range(1,n + 1):\n",
    "                dp[j][1] = cost[0][j - 1]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            color = houses[i]\n",
    "            tmp = dp.copy()\n",
    "            dp = [[inf] * (target + 1) for _ in range(n + 1)]\n",
    "            if color == 0:\n",
    "                for j1 in range(1,n + 1):\n",
    "                    for k in range(1,target + 1):\n",
    "                        for j2 in range(1,n + 1):\n",
    "                            if j1 == j2: \n",
    "                                dp[j1][k] = min(dp[j1][k],tmp[j2][k] + cost[i][j1-1])\n",
    "                            else:\n",
    "                                dp[j1][k] = min(dp[j1][k],tmp[j2][k-1] + cost[i][j1-1])\n",
    "            else:\n",
    "                for k in range(1,target + 1):\n",
    "                    for j2 in range(1, n + 1):\n",
    "                        if j2 == color:\n",
    "                            dp[color][k] = min(dp[color][k],tmp[j2][k])\n",
    "                        else:\n",
    "                            dp[color][k] = min(dp[color][k],tmp[j2][k-1])\n",
    "\n",
    "        ans = inf\n",
    "        for j in range(1, n + 1):\n",
    "            ans = min(ans,dp[j][target])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        pre_cost = dict()\n",
    "        for i, hcolor in enumerate(houses):\n",
    "            cur_cost = dict()\n",
    "            if i == 0:\n",
    "                if hcolor == 0:\n",
    "                    for j in range(1, n + 1):\n",
    "                        cur_cost[(j, 1)] = cost[i][j - 1]\n",
    "                else:\n",
    "                    cur_cost[(hcolor, 1)] = 0\n",
    "            else:\n",
    "                if hcolor == 0:\n",
    "                    for j in range(1, n + 1):\n",
    "                        for (pre_color, pre_cnt), pre_mcost in pre_cost.items():\n",
    "                            cnt = pre_cnt + 1 if pre_color != j else pre_cnt\n",
    "                            key = (j, cnt)\n",
    "                            ccost = pre_mcost + cost[i][j - 1]\n",
    "                            if key not in cur_cost or cur_cost[key] > ccost:\n",
    "                                cur_cost[key] = ccost\n",
    "                else:\n",
    "                    for (pre_color, pre_cnt), pre_mcost in pre_cost.items():\n",
    "                        cnt = pre_cnt + 1 if pre_color != hcolor else pre_cnt\n",
    "                        key = (hcolor, cnt)\n",
    "                        ccost = pre_mcost\n",
    "                        if key not in cur_cost or cur_cost[key] > ccost:\n",
    "                            cur_cost[key] = ccost\n",
    "\n",
    "            pre_cost = cur_cost\n",
    "\n",
    "        res = -1\n",
    "        for j in range(1, n + 1):\n",
    "            if (j, target) in pre_cost:\n",
    "                if res == -1 or (res >= 0 and pre_cost[(j, target)] < res):\n",
    "                    res = pre_cost[(j, target)]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i+1),1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "                    '''\n",
    "                    for t in range(min_,target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(max(min_,1),target):\n",
    "                            dp[i][t][j] = min(dp[i][t][j], dp[i-1][t-1][(j+k)%n] + cost[i][j])\n",
    "                    '''\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "                '''\n",
    "                for t in range(min_,target):\n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(max(min_,1),target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t-1][(j+k)%n])\n",
    "                '''\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i+1),0)\n",
    "            min__ = max(target-(m-i+1)-1,0)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    if min_ == 0:\n",
    "                        dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "                        min_ = 1\n",
    "                    for t in range(min_,target):\n",
    "                        \n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                        \n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(min__,target-1):\n",
    "                            dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if min_ == 0:\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "                    min_ = 1\n",
    "                for t in range(min_,target):\n",
    "                    \n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                    \n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(min__,target-1):\n",
    "                        dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_ = max(target-(m-i-1),1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(dp[i_][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i_][0][j] = min(dp[i_][0][j], dp[i__][0][j] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(dp[i_][t][j], min(tmp))\n",
    "                dp[i_][0][j] = min(dp[i_][0][j], dp[i__][0][j])\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i-1)-1,1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i+1),0)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(max(min_,1),target):\n",
    "                            dp[i][t][j] = min(dp[i][t][j], dp[i-1][t-1][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(max(min_,1),target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t-1][(j+k)%n])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i+1),0)\n",
    "            min__ = max(target-(m-i+1)-1,0)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    if min_ == 0:\n",
    "                        dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "                        min_ = 1\n",
    "                    for t in range(min_,target):\n",
    "                        \n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                        \n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(min__,target-1):\n",
    "                            dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if min_ == 0:\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "                    min_ = 1\n",
    "                for t in range(min_,target):\n",
    "                    \n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                    \n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(min__,target-1):\n",
    "                        dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i+1),0)\n",
    "            min__ = max(target-(m-i+1)-1,0)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(min__,target-1):\n",
    "                            dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(min__,target-1):\n",
    "                        dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            #dp[i_] = [[1e6+1]*n for j in range(target)]\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            print(dp[i_])\n",
    "            print(min_t,max_t)\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i__,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_two_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = min(dp[i__][t-1][min_one_idx], dp[i__][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i_][t][j] = dp[i__][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i_][t][j] = dp[i__][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i_][0][min_idx] = dp[i__][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp)\n",
    "                    dp[i_][0][j] = dp[i__][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i_][t][j] = dp[i__][t][j]\n",
    "                        else:\n",
    "                            dp[i_][t][j] = dp[i__][t-1][min_idx]\n",
    "                    if j == min_idx:\n",
    "                        dp[i_][0][min_idx] = dp[i__][0][min_idx]\n",
    "            print(dp[i_])\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            tmp = dp[i-1][t-1]\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i-1,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_two_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_one_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i][t][j] = dp[i-1][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = dp[i-1][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i][0][min_idx] = dp[i-1][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp)\n",
    "                    dp[i][0][j] = dp[i-1][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = dp[i-1][t][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = dp[i-1][t-1][min_idx]\n",
    "                    if j == min_idx:\n",
    "                        dp[i][0][min_idx] = dp[i-1][0][min_idx]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1]\n",
    "                    min_idx = -1\n",
    "                    min_idx_ = -1\n",
    "                    for j in range(n):\n",
    "                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:\n",
    "                            min_idx_ = min_idx\n",
    "                            min_idx = j\n",
    "                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:\n",
    "                            min_idx_ = j\n",
    "                    for j in range(n):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                '''\n",
    "                for t in range(min_t,max_t):\n",
    "                    for j in range(n):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                '''\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            if houses[i] == 0:\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1]\n",
    "                    min_idx = -1\n",
    "                    min_idx_ = -1\n",
    "                    for j in range(n):\n",
    "                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:\n",
    "                            min_idx_ = min_idx\n",
    "                            min_idx = j\n",
    "                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:\n",
    "                            min_idx_ = j\n",
    "                    for j in range(n):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_ = max(target-(m-i-1),1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(dp[i_][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i_][0][j] = min(dp[i_][0][j], dp[i__][0][j] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(dp[i_][t][j], min(tmp))\n",
    "                dp[i_][0][j] = min(dp[i_][0][j], dp[i__][0][j])\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_ = max(target-(m-i),1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                '''\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1]\n",
    "                    min_idx = -1\n",
    "                    min_idx_ = -1\n",
    "                    for j in range(n):\n",
    "                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:\n",
    "                            min_idx_ = min_idx\n",
    "                            min_idx = j\n",
    "                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:\n",
    "                            min_idx_ = j\n",
    "                    for j in range(n):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                '''\n",
    "                for t in range(min_t,max_t):\n",
    "                    for j in range(n):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1]\n",
    "                    min_idx = -1\n",
    "                    min_idx_ = -1\n",
    "                    for j in range(n):\n",
    "                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:\n",
    "                            min_idx_ = min_idx\n",
    "                            min_idx = j\n",
    "                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:\n",
    "                            min_idx_ = j\n",
    "                    for j in range(n):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                '''\n",
    "                for t in range(min_t,max_t):\n",
    "                    for j in range(n):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                '''\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        \n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for t in range(min_t,max_t):\n",
    "                    '''\n",
    "                    tmp = dp[i-1][t-1]\n",
    "                    min_idx = -1\n",
    "                    min_idx_ = -1\n",
    "                    for j in range(n):\n",
    "                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:\n",
    "                            min_idx_ = min_idx\n",
    "                            min_idx = j\n",
    "                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:\n",
    "                            min_idx_ = j\n",
    "                    '''\n",
    "                    for j in range(n):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                        '''\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                        '''\n",
    "                    dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_ = max(target-(m-i-1)-1,1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_ = max(target-(m-i-1)-1,1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(dp[i][t][j], min(tmp) + cost[i][j])\n",
    "                    dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(dp[i][t][j], min(tmp))\n",
    "                dp[i][0][j] = min(dp[i][0][j], dp[i-1][0][j])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        \n",
    "        def find_two_most_min(i,t):\n",
    "            tmp = dp[i-1][t-1]\n",
    "            min_one_idx = -1\n",
    "            min_two_idx = -1\n",
    "            for j in range(n):\n",
    "                if min_one_idx == -1 or dp[i][t][min_one_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = min_one_idx\n",
    "                    min_one_idx = j\n",
    "                elif min_two_idx == -1 or dp[i][t][min_two_idx] >= dp[i][t][j]:\n",
    "                    min_two_idx = j\n",
    "            return min_one_idx, min_two_idx\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+1)\n",
    "            if houses[i] == 0:\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        min_one_idx, min_two_idx = find_two_most_min(i-1,t-1)\n",
    "                        for j in range(n):\n",
    "                            if j == min_one_idx:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_two_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = min(dp[i-1][t-1][min_one_idx], dp[i-1][t][j]) + cost[i][j]\n",
    "                    for j in range(n):\n",
    "                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        for j in range(n):\n",
    "                            if j == min_idx:\n",
    "                                dp[i][t][j] = dp[i-1][t][j] + cost[i][j]\n",
    "                            else:\n",
    "                                dp[i][t][j] = dp[i-1][t-1][min_idx] + cost[i][j]\n",
    "                    dp[i][0][min_idx] = dp[i-1][0][min_idx] + cost[i][min_idx]\n",
    "                \n",
    "                # for t in range(min_t,max_t):\n",
    "                #     for j in range(n):\n",
    "                #         tmp = dp[i-1][t-1][:]\n",
    "                #         tmp[j] = dp[i-1][t][j]\n",
    "                #         dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                #         dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "                \n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                if houses[i-1] == 0:\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp)\n",
    "                    dp[i][0][j] = dp[i-1][0][j]\n",
    "                else:\n",
    "                    min_idx = houses[i-1]-1\n",
    "                    for t in range(min_t,max_t):\n",
    "                        if j == min_idx:\n",
    "                            dp[i][t][j] = dp[i-1][t][j]\n",
    "                        else:\n",
    "                            dp[i][t][j] = dp[i-1][t-1][min_idx]\n",
    "                    dp[i][0][min_idx] = dp[i-1][0][min_idx]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从0开始编号，没有被涂色标记为-1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "\n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "                    \n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "        \n",
    "        ans = min(dp[m- 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        \n",
    "        block_cost = defaultdict(int)\n",
    "\n",
    "        '''\n",
    "        第一维: 第i间房子\n",
    "        第二维: 染成第c个颜色\n",
    "        第三位: 形成了t个街区\n",
    "        '''\n",
    "        '''\n",
    "        主要是遍历一个房子和前面的房子是否有一样的颜色, 如果一样, 就是一个街区\n",
    "        如果不一样, 那么街区数目就+1\n",
    "        '''\n",
    "        dp = [[[inf] * (target + 1) for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        # 第0间房子  \n",
    "        if houses[0]:\n",
    "            dp[0][houses[0]-1][1] = 0\n",
    "        else:\n",
    "            for c in range(n):\n",
    "                dp[0][c][1] = cost[0][c]\n",
    "        \n",
    "        for i in range(1,m): # 遍历所有房子\n",
    "            c = houses[i]\n",
    "            if c: # 已经染色了  \n",
    "                # 由于颜色是从1开始编号, 要记得-1\n",
    "                for prec in range(n):\n",
    "                    if c-1 == prec: # 这个房子和前一个在一个街区\n",
    "                        for t in range(1, target+1):\n",
    "                            dp[i][c-1][t] = min(dp[i][c-1][t], dp[i-1][prec][t])\n",
    "                    else:\n",
    "                        for t in range(1, target+1):\n",
    "                            dp[i][c-1][t] = min(dp[i][c-1][t], dp[i-1][prec][t-1])\n",
    "            else: #没有染色\n",
    "                for cc in range(n):\n",
    "                    for prec in range(n):\n",
    "                        if cc == prec: # 同一个街区\n",
    "                            for t in range(1, target+1):\n",
    "                                dp[i][cc][t] = min(dp[i][cc][t], dp[i-1][prec][t] + cost[i][cc])\n",
    "                        else:\n",
    "                            for t in range(1, target+1):\n",
    "                                dp[i][cc][t] = min(dp[i][cc][t], dp[i-1][prec][t-1] + cost[i][cc])\n",
    "        ans = inf\n",
    "        for c in range(n):\n",
    "            ans = min(ans, dp[-1][c][-1])\n",
    "        return -1 if ans is inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [ [ [ inf ] * (target+1) for _ in range(n) ] for _ in range(m) ]\n",
    "        if houses[0] == 0:\n",
    "            for j in range(n):\n",
    "                dp[0][j][1] = cost[0][j]\n",
    "        else:\n",
    "            dp[0][houses[0]-1][1] = 0\n",
    "\n",
    "        for i in range(1, m):\n",
    "            # 已经涂色，不可以重新涂\n",
    "            if houses[i] != 0:\n",
    "                c = houses[i] - 1\n",
    "                for j in range(n):\n",
    "                    for t in range(1, target+1):\n",
    "                        if j == c:\n",
    "                            dp[i][c][t] = min(dp[i][c][t], dp[i-1][c][t])\n",
    "                        else:\n",
    "                            dp[i][c][t] = min(dp[i][c][t], dp[i-1][j][t-1])\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    for t in range(1, target+1):\n",
    "                        for k in range(n):\n",
    "                            if k == j:\n",
    "                                dp[i][j][t] = min(dp[i][j][t], dp[i-1][k][t] + cost[i][j])\n",
    "                            else:\n",
    "                                dp[i][j][t] = min(dp[i][j][t], dp[i-1][k][t-1] + cost[i][j])\n",
    "        ans = inf\n",
    "        for j in range(n):\n",
    "            ans = min(ans, dp[-1][j][target])\n",
    "        return ans if ans != inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        \n",
    "        block_cost = defaultdict(int)\n",
    "        dp = [[[inf] * (target + 1) for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        # 第0间房子  \n",
    "        if houses[0]:\n",
    "            dp[0][houses[0]-1][1] = 0\n",
    "        else:\n",
    "            for c in range(n):\n",
    "                dp[0][c][1] = cost[0][c]\n",
    "        \n",
    "        for i in range(1,m): # 遍历所有房子\n",
    "            c = houses[i]\n",
    "            if c: # 已经染色了  \n",
    "                # 由于颜色是从1开始编号, 要记得-1\n",
    "                for prec in range(n):\n",
    "                    if c-1 == prec: # 这个房子和前一个在一个街区\n",
    "                        for t in range(1, target+1):\n",
    "                            dp[i][c-1][t] = min(dp[i][c-1][t], dp[i-1][prec][t])\n",
    "                    else:\n",
    "                        for t in range(1, target+1):\n",
    "                            dp[i][c-1][t] = min(dp[i][c-1][t], dp[i-1][prec][t-1])\n",
    "            else: #没有染色\n",
    "                for cc in range(n):\n",
    "                    for prec in range(n):\n",
    "                        if cc == prec: # 同一个街区\n",
    "                            for t in range(1, target+1):\n",
    "                                dp[i][cc][t] = min(dp[i][cc][t], dp[i-1][prec][t] + cost[i][cc])\n",
    "                        else:\n",
    "                            for t in range(1, target+1):\n",
    "                                dp[i][cc][t] = min(dp[i][cc][t], dp[i-1][prec][t-1] + cost[i][cc])\n",
    "        ans = inf\n",
    "        for c in range(n):\n",
    "            ans = min(ans, dp[-1][c][-1])\n",
    "        return -1 if ans is inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "\n",
    "        dp = [[[float('inf')] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "\n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "                    \n",
    "                    if dp[i][j][k] != float('inf') and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        m = len(houses)\n",
    "        n = len(cost[0])\n",
    "\n",
    "        houses = [c-1 for c in houses]\n",
    "        dp = [[[float('inf')]*target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for  j in range(n):\n",
    "                if houses[i]!=-1 and houses[i]!=j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j==j0:\n",
    "                            if i==0:\n",
    "                                if k==0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])\n",
    "                        else:\n",
    "                            if i>0 and k>0:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j0][k-1])\n",
    "                    if dp[i][j][k]!=float('inf') and houses[i]==-1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min([dp[m-1][j][target-1] for j in range(n)])\n",
    "        return -1 if ans==float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从 0 开始编号，没有被涂色标记为 -1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                \n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "\n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "\n",
    "        ans = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 将颜色调整为从0开始编号，没有被涂色标记为-1\n",
    "        houses = [c - 1 for c in houses]\n",
    "\n",
    "        # dp 所有元素初始化为极大值\n",
    "        dp = [[[float(\"inf\")] * target for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "\n",
    "                for k in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j == j0:\n",
    "                            if i == 0:\n",
    "                                if k == 0:\n",
    "                                    dp[i][j][k] = 0\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])\n",
    "                        elif i > 0 and k > 0:\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])\n",
    "                    \n",
    "                    if dp[i][j][k] != float(\"inf\") and houses[i] == -1:\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "        \n",
    "        ans = min(dp[m- 1][j][target - 1] for j in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(target-1):\n",
    "                            dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(target):\n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(target-1):\n",
    "                        dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n])\n",
    "            #print(dp)\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 排除一些特殊情况\n",
    "        if m < target:\n",
    "            return -1\n",
    "        elif m == 1 and target == 1:\n",
    "            if houses[0] != 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return cost[0][0]\n",
    "\n",
    "        # 3维的动态规划\n",
    "        INF = 10 ** 9\n",
    "\n",
    "        # 初始化dp数组\n",
    "        dp = [[[INF for _ in range(target + 1)] for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        # 对某些数值进一步初始化,即 房屋编号为0且分区为0的dp——初始化易导致出错\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j][0] = 0\n",
    "\n",
    "        # 开始dp\n",
    "        # 首先遍历房子序号\n",
    "        for i in range(m + 1):\n",
    "            color = houses[i - 1]\n",
    "            # 接着遍历决策颜色与分区\n",
    "            for j in range(1, n + 1):\n",
    "                partitionEnd = min(i + 1, target + 1)\n",
    "                for k in range(1, partitionEnd):\n",
    "                    # 如果可以涂色,从不新增分区与新增分区中找到min值,再加上cost\n",
    "                    if color == 0:\n",
    "                        # 1、不新增分区\n",
    "                        tmp1 = dp[i - 1][j][k]\n",
    "                        \n",
    "                        #2、新增分区\n",
    "                        tmp2 = INF\n",
    "                        for p in range(1, n + 1):\n",
    "                            # 这个地方易错,等式右侧是j而不是color！！！！\n",
    "                            if p != j:\n",
    "                                tmp2 = min(tmp2, dp[i - 1][p][k - 1])\n",
    "                        \n",
    "                        # 当前取值即为\n",
    "                        dp[i][j][k] = min(tmp1, tmp2) + cost[i - 1][j - 1]\n",
    "                        \n",
    "                    # 如果不可以涂色\n",
    "                    else:\n",
    "                        # 如果决策的颜色不同于当前颜色\n",
    "                        if j != color:\n",
    "                            dp[i][j][k] = INF\n",
    "                        else:\n",
    "                            # 1、不新增分区\n",
    "                            tmp1 = dp[i - 1][j][k]\n",
    "                            \n",
    "                            #2、新增分区\n",
    "                            tmp2 = INF\n",
    "                            for p in range(1, n + 1):\n",
    "                            # 这个地方易错,等式右侧是j而不是color！！！！\n",
    "                                if p != j:\n",
    "                                    tmp2 = min(tmp2, dp[i - 1][p][k - 1])\n",
    "                            \n",
    "                            # 当前取值即为\n",
    "                            dp[i][j][k] = min(tmp1, tmp2)\n",
    "        # print(dp)\n",
    "\n",
    "        # 得到结果\n",
    "        ans = INF\n",
    "        for j in range(1, n + 1):\n",
    "            ans = min(ans, dp[m][j][target])\n",
    "        if ans != INF:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        def auxFun(dp, i, j, k):\n",
    "            value = float('inf')\n",
    "            for t in range(n):\n",
    "                if t == j:\n",
    "                    continue\n",
    "                if dp[i][t][k] < value:\n",
    "                    value = dp[i][t][k]\n",
    "            \n",
    "            return value\n",
    "        \n",
    "        dp = [[[float('inf')] * target for _ in  range(n)] for _ in range(m)]\n",
    "        \n",
    "        if houses[0] == 0:\n",
    "            for j in range(n):\n",
    "                dp[0][j][0] = cost[0][j]\n",
    "        else:\n",
    "            dp[0][houses[0]-1][0] = 0\n",
    "            \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if houses[i] == 0:\n",
    "                    dp[i][j][0] = dp[i-1][j][0] + cost[i][j]\n",
    "                elif houses[i] == j+1:\n",
    "                    dp[i][j][0] = dp[i-1][j][0]\n",
    "        \n",
    "        for k in range(1, target):\n",
    "            for i in range(k, m):\n",
    "                for j in range(n):\n",
    "                    if houses[i] == 0:\n",
    "                        dp[i][j][k] = min(dp[i-1][j][k], auxFun(dp, i-1, j, k-1)) + cost[i][j]\n",
    "                    elif houses[i] == j+1:\n",
    "                        dp[i][j][k] = min(dp[i-1][j][k], auxFun(dp, i-1, j, k-1))\n",
    "                        \n",
    "        value = min([dp[m-1][j][target-1] for j in range(n)])\n",
    "        return value if value != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        INF = float(\"inf\")\n",
    "        f = [[[0]*(target+1) for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                f[i][j][0] = INF\n",
    "        for i in range(1, m+1):\n",
    "            color = houses[i-1]\n",
    "            for j in range(1, n+1):\n",
    "                for k in range(1, target +1):\n",
    "                    if(k>i):\n",
    "                        f[i][j][k] = INF\n",
    "                        continue\n",
    "                    if color != 0:\n",
    "                        if j== color:\n",
    "                           \n",
    "                            tmp = INF\n",
    "                            for p in range(1,n+1):\n",
    "                                if (p!=j):\n",
    "                                    tmp = min(tmp, f[i-1][p][k-1])\n",
    "                            f[i][j][k] = min(f[i-1][j][k],tmp)\n",
    "                        else:\n",
    "                            f[i][j][k] = INF\n",
    "                    else:\n",
    "                        u = cost[i-1][j-1]\n",
    "                        tmp = INF\n",
    "                        for p in range(1, n+1):\n",
    "                            if p!=j:\n",
    "                                tmp = min(tmp, f[i-1][p][k-1])\n",
    "                        f[i][j][k] = min(f[i-1][j][k], tmp) + u\n",
    "\n",
    "        res = INF\n",
    "        for i in range(1, n+1):\n",
    "            res = min(res,f[m][i][target])\n",
    "        return -1 if res == INF else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)]\n",
    "        if houses[0] != 0:\n",
    "            dp[0][houses[0]][1] = 0\n",
    "        else:\n",
    "            for j in range(1,n + 1):\n",
    "                dp[0][j][1] = cost[0][j - 1]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            color = houses[i]\n",
    "            if color == 0:\n",
    "                for j1 in range(1,n + 1):\n",
    "                    for k in range(1,target + 1):\n",
    "                        for j2 in range(1,n + 1):\n",
    "                            if j1 == j2: \n",
    "                                dp[i][j1][k] = min(dp[i][j1][k],dp[i-1][j2][k] + cost[i][j1-1])\n",
    "                            else:\n",
    "                                dp[i][j1][k] = min(dp[i][j1][k],dp[i-1][j2][k-1]+cost[i][j1-1])\n",
    "            else:\n",
    "                for k in range(1,target + 1):\n",
    "                    for j2 in range(1, n + 1):\n",
    "                        if j2 == color:\n",
    "                            dp[i][j2][k] = min(dp[i][j2][k],dp[i-1][j2][k])\n",
    "                        else:\n",
    "                            dp[i][color][k] = min(dp[i][color][k],dp[i-1][j2][k-1])\n",
    "\n",
    "        ans = inf\n",
    "        for j in range(1, n + 1):\n",
    "            ans = min(ans,dp[-1][j][target])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(target):\n",
    "                        dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j] + cost[i][j])\n",
    "                    for k in range(1,n):\n",
    "                        for t in range(target-1):\n",
    "                            dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n] + cost[i][j])\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(target):\n",
    "                    dp[i][t][j] = min(dp[i][t][j], dp[i-1][t][j])\n",
    "                for k in range(1,n):\n",
    "                    for t in range(target-1):\n",
    "                        dp[i][t+1][j] = min(dp[i][t+1][j], dp[i-1][t][(j+k)%n])\n",
    "        res = min(dp[-1][-1])\n",
    "        if res == 1e6+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "\n",
    "        m = len(houses)\n",
    "        dp = [[[inf] * (n + 1) for _ in range(target + 1)] for _ in range(m + 1)]\n",
    "        dp[0][0] = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            cur = houses[i - 1]\n",
    "            if cur != 0:\n",
    "                for t in range(1, target + 1):\n",
    "                    for j in range(n + 1):\n",
    "                        if j == cur:\n",
    "                            dp[i][t][cur] = min(dp[i][t][cur], dp[i - 1][t][cur])\n",
    "                        else:\n",
    "                            dp[i][t][cur] = min(dp[i][t][cur], dp[i - 1][t - 1][j])\n",
    "            else:\n",
    "                for t in range(1, target + 1):\n",
    "                    for j in range(1, n + 1):\n",
    "                        for k in range(n + 1):\n",
    "                            if j == k:\n",
    "                                dp[i][t][j] = min(dp[i][t][j], dp[i - 1][t][j] + cost[i - 1][j - 1])\n",
    "                            else:\n",
    "                                dp[i][t][j] = min(dp[i][t][j], dp[i - 1][t - 1][k] + cost[i - 1][j - 1])\n",
    "                                \n",
    "        # print(dp)\n",
    "        ans = inf\n",
    "        for i in range(n + 1):\n",
    "            ans = min(ans, dp[m][target][i])\n",
    "        \n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "\n",
    "        m = len(houses)\n",
    "        dp = [[[inf] * (n + 1) for _ in range(target + 1)] for _ in range(m + 1)]\n",
    "        dp[0][0] = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            cur = houses[i - 1]\n",
    "            if cur != 0:\n",
    "                for t in range(1, target + 1):\n",
    "                    for j in range(n + 1):\n",
    "                        if j == cur:\n",
    "                            dp[i][t][cur] = min(dp[i][t][cur], dp[i - 1][t][cur])\n",
    "                        else:\n",
    "                            dp[i][t][cur] = min(dp[i][t][cur], dp[i - 1][t - 1][j])\n",
    "            else:\n",
    "                for t in range(1, target + 1):\n",
    "                    for j in range(1, n + 1):\n",
    "                        for k in range(n + 1):\n",
    "                            if j == k:\n",
    "                                dp[i][t][j] = min(dp[i][t][j], dp[i - 1][t][j] + cost[i - 1][j - 1])\n",
    "                            else:\n",
    "                                dp[i][t][j] = min(dp[i][t][j], dp[i - 1][t - 1][k] + cost[i - 1][j - 1])\n",
    "                                \n",
    "        # print(dp)\n",
    "        ans = inf\n",
    "        for i in range(n + 1):\n",
    "            ans = min(ans, dp[m][target][i])\n",
    "        \n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "\n",
    "\n",
    "        #dp[i][j][k] # house i, already j neghbors, last painted as k \n",
    "\n",
    "        dp = [ [[float(\"inf\") ]*(n+1)  for _ in range(target+1)] for _ in range(m)]\n",
    "\n",
    "        if houses[0]==0:\n",
    "            for k in range(1,n+1):\n",
    "                dp[0][1][k] = cost[0][k-1]\n",
    "        else:\n",
    "            color = houses[0]\n",
    "            dp[0][1][color] = 0\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            color = houses[i]\n",
    "            if color>0:\n",
    "\n",
    "                for j in range(1,target+1):\n",
    "                    for prev_color in range(1,n+1):\n",
    "                        if color==prev_color:\n",
    "                            dp[i][j][color] = min(dp[i][j][color], dp[i-1][j][prev_color])\n",
    "                        else:\n",
    "                            dp[i][j][color] = min( dp[i][j][color], dp[i-1][j-1][prev_color])\n",
    "            else:\n",
    "\n",
    "                for j in range(1,target+1):\n",
    "                    for k in range(1,n+1):\n",
    "                        for prev_k in range(1,n+1):\n",
    "                            if prev_k==k:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k]+cost[i][k-1])\n",
    "                            else:\n",
    "                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][prev_k]+cost[i][k-1])\n",
    "\n",
    "        ans =  min(dp[m-1][target])\n",
    "\n",
    "        #print(dp[2][3][1],dp[1][2][3])\n",
    "        return ans if ans<float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "      '''\n",
    "      定义状态\n",
    "      f[i][j][k] 定义为前i个房子，j个街区，当前为颜色k的最小花费\n",
    "\n",
    "      状态转移分为两种情况\n",
    "      1.当前颜色可以修改\n",
    "      2.当前颜色不能修改\n",
    "\n",
    "      1.可以修改：\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用增加cost[k]\n",
    "            街区数量加1，颜色为当前颜色，费用增加cost[k]\n",
    "\n",
    "      2.不能修改\n",
    "         假设当前颜色为cur\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用不变\n",
    "            街区数量加1，颜色为当前颜色，费用不变\n",
    "      '''\n",
    "      #状态方程\n",
    "      f=[[[float('inf')]*(n+1)for _ in range(target+1)]for _ in range(m+1)]\n",
    "      \n",
    "      for j in range(n+1):\n",
    "        f[0][0][j]=0\n",
    "\n",
    "      for i in range(1,m+1):#从第一个房子到第n个房子遍历\n",
    "        for j in range(1,min(target,i)+1):#遍历街区数量\n",
    "          if houses[i-1]:#已经涂色\n",
    "            cur=houses[i-1]\n",
    "            for k in range(0,n+1):#遍历前一个房子的颜色\n",
    "              if cur==k:#颜色相同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k])\n",
    "              else:#颜色不同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k])\n",
    "          else:#没有涂色\n",
    "            for cur in range(1,n+1):#遍历当前颜色\n",
    "              for k in range(n+1):#遍历前一个房子的颜色\n",
    "                if cur==k:#颜色相同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k]+cost[i-1][cur-1])\n",
    "                else:#颜色不同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k]+cost[i-1][cur-1])\n",
    "      \n",
    "      res=min(f[m][target])\n",
    "      #print(f[m][target])\n",
    "      return -1 if res==float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, pre, cnt):\n",
    "            if i == m:\n",
    "                return 0 if cnt == target else inf\n",
    "            if cnt > target:\n",
    "                return inf\n",
    "            if m-i+cnt < target:\n",
    "                return inf\n",
    "            if houses[i]:\n",
    "                return dfs(i+1, houses[i]-1, cnt+int(pre!=houses[i]-1))\n",
    "            res = inf\n",
    "            for j in range(n):\n",
    "                cur = dfs(i+1, j, cnt+int(pre!=j)) + cost[i][j]\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, -1, 0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[10**7 for _ in range(n+1)] for __ in range(target+1)] for ___ in range(m)]\n",
    "        if houses[0] ==0:\n",
    "            for k in range(1,n+1):\n",
    "                dp[0][1][k] = cost[0][k-1]\n",
    "        else:\n",
    "            dp[0][1][houses[0]] = 0 \n",
    "        for i in range(1,m):\n",
    "            if houses[i] != 0:\n",
    "                for t in range(1,min(i+2,target+1)):\n",
    "                    dp[i][t][houses[i]] = min([dp[i-1][t-1][c] for c in range(1,n+1) if c != houses[i]])\n",
    "                    dp[i][t][houses[i]] = min(dp[i][t][houses[i]],dp[i-1][t][houses[i]])\n",
    "            else:\n",
    "                for t in range(1,min(i+2,target+1)):\n",
    "                    for k in range(1,n+1):\n",
    "                        dp[i][t][k] = min([dp[i-1][t-1][c] for c in range(1,n+1) if c != k])\n",
    "                        dp[i][t][k] = min(dp[i][t][k],dp[i-1][t][k]) + cost[i][k-1]\n",
    "\n",
    "        return min(dp[m-1][target]) if min(dp[m-1][target]) != 10**7 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "      '''\n",
    "      定义状态\n",
    "      f[i][j][k] 定义为前i个房子，j个街区，当前为颜色k的最小花费\n",
    "\n",
    "      状态转移分为两种情况\n",
    "      1.当前颜色可以修改\n",
    "      2.当前颜色不能修改\n",
    "\n",
    "      1.可以修改：\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用增加cost[k]\n",
    "            街区数量加1，颜色为当前颜色，费用增加cost[k]\n",
    "\n",
    "      2.不能修改\n",
    "         假设当前颜色为cur\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用不变\n",
    "            街区数量加1，颜色为当前颜色，费用不变\n",
    "      '''\n",
    "      #状态方程\n",
    "      f=[[[float('inf')]*(n+1)for _ in range(target+1)]for _ in range(m+1)]\n",
    "      \n",
    "      for j in range(n+1):\n",
    "        f[0][0][j]=0\n",
    "\n",
    "      for i in range(1,m+1):#从第一个房子到第n个房子遍历\n",
    "        for j in range(1,target+1):#遍历街区数量\n",
    "          if houses[i-1]:#已经涂色\n",
    "            cur=houses[i-1]\n",
    "            for k in range(0,n+1):#遍历前一个房子的颜色\n",
    "              if cur==k:#颜色相同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k])\n",
    "              else:#颜色不同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k])\n",
    "          else:#没有涂色\n",
    "            for cur in range(1,n+1):#遍历当前颜色\n",
    "              for k in range(n+1):#遍历前一个房子的颜色\n",
    "                if cur==k:#颜色相同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k]+cost[i-1][cur-1])\n",
    "                else:#颜色不同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k]+cost[i-1][cur-1])\n",
    "      \n",
    "      res=min(f[m][target])\n",
    "      print(f[m][target])\n",
    "      return -1 if res==float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "      '''\n",
    "      定义状态\n",
    "      f[i][j][k] 定义为前i个房子，j个街区，当前为颜色k的最小花费\n",
    "\n",
    "      状态转移分为两种情况\n",
    "      1.当前颜色可以修改\n",
    "      2.当前颜色不能修改\n",
    "\n",
    "      1.可以修改：\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用增加cost[k]\n",
    "            街区数量加1，颜色为当前颜色，费用增加cost[k]\n",
    "\n",
    "      2.不能修改\n",
    "         假设当前颜色为cur\n",
    "          又能分为两种情况：\n",
    "          当前颜色与前一个状态颜色相同：\n",
    "            街区数量不变，颜色不变，费用不变\n",
    "            街区数量加1，颜色为当前颜色，费用不变\n",
    "      '''\n",
    "      #状态方程\n",
    "      f=[[[float('inf')]*(n+1)for _ in range(target+1)]for _ in range(m+1)]\n",
    "      \n",
    "      for j in range(n+1):\n",
    "        f[0][0][j]=0\n",
    "\n",
    "      for i in range(1,m+1):#从第一个房子到第n个房子遍历\n",
    "        for j in range(1,min(target,i)+1):#遍历街区数量\n",
    "          if houses[i-1]:#已经涂色\n",
    "            cur=houses[i-1]\n",
    "            for k in range(0,n+1):#遍历前一个房子的颜色\n",
    "              if cur==k:#颜色相同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k])\n",
    "              else:#颜色不同\n",
    "                f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k])\n",
    "          else:#没有涂色\n",
    "            for cur in range(1,n+1):#遍历当前颜色\n",
    "              for k in range(n+1):#遍历前一个房子的颜色\n",
    "                if cur==k:#颜色相同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j][k]+cost[i-1][cur-1])\n",
    "                else:#颜色不同\n",
    "                  f[i][j][cur]=min(f[i][j][cur],f[i-1][j-1][k]+cost[i-1][cur-1])\n",
    "      \n",
    "      res=min(f[m][target])\n",
    "      print(f[m][target])\n",
    "      return -1 if res==float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[10**7 for _ in range(n+1)] for __ in range(target+1)] for ___ in range(m)]\n",
    "        if houses[0] ==0:\n",
    "            for k in range(1,n+1):\n",
    "                dp[0][1][k] = cost[0][k-1]\n",
    "        else:\n",
    "            dp[0][1][houses[0]] = 0 \n",
    "        for i in range(1,m):\n",
    "            if houses[i] != 0:\n",
    "                for t in range(1,min(i+2,target+1)):\n",
    "                    dp[i][t][houses[i]] = min([dp[i-1][t-1][c] for c in range(1,n+1) if c != houses[i]])\n",
    "                    dp[i][t][houses[i]] = min(dp[i][t][houses[i]],dp[i-1][t][houses[i]])\n",
    "            else:\n",
    "                for t in range(1,min(i+2,target+1)):\n",
    "                    for k in range(1,n+1):\n",
    "                        dp[i][t][k] = min([dp[i-1][t-1][c] for c in range(1,n+1) if c != k])\n",
    "                        dp[i][t][k] = min(dp[i][t][k],dp[i-1][t][k]) + cost[i][k-1]\n",
    "\n",
    "        return min(dp[m-1][target]) if min(dp[m-1][target]) != 10**7 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        for i in range(m):\n",
    "            if houses[i] != 0:\n",
    "                cost[i][houses[i]-1] = 0\n",
    "        @cache\n",
    "        def f(indx, c, k):\n",
    "            if houses[indx] != 0 and c != houses[indx]:\n",
    "                return inf\n",
    "            if k == 1:\n",
    "                sm = 0\n",
    "                for i in range(indx,m):\n",
    "                    if houses[i] != 0 and houses[i] != c:\n",
    "                        return inf\n",
    "                    sm += cost[i][c-1]\n",
    "                return sm\n",
    "\n",
    "            res = inf\n",
    "\n",
    "            for n_c in range(1,n+1):\n",
    "                if n_c == c:\n",
    "                    continue\n",
    "                for i in range(indx,m-k+1):\n",
    "                    if houses[i] != 0 and houses[i] != c:\n",
    "                        break\n",
    "                    res = min(res, sum([ a[c-1] for a in cost[indx:i+1] ]) + f(i+1, n_c, k-1))\n",
    "            return res\n",
    "\n",
    "        res = inf\n",
    "        for c in range(1,n+1):\n",
    "            res = min(res, f(0,c,target))\n",
    "        return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, color, t):\n",
    "            if t < 0 or t > m - idx:\n",
    "                return float(\"inf\")\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            curr = float(\"inf\")\n",
    "            if houses[idx]:\n",
    "                if houses[idx] != color:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t - 1))\n",
    "                else:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t))\n",
    "            else:\n",
    "                for i in range(1, n + 1):\n",
    "                    if i != color:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t - 1) + cost[idx][i - 1])\n",
    "                    else:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t) + cost[idx][i - 1])\n",
    "            return curr\n",
    "\n",
    "        res = dfs(0, 0, target)\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, color, t):\n",
    "            if t < 0 or t > m - idx:\n",
    "                return float(\"inf\")\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            curr = float(\"inf\")\n",
    "            if houses[idx]:\n",
    "                if houses[idx] != color:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t - 1))\n",
    "                else:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t))\n",
    "            else:\n",
    "                for i in range(1, n + 1):\n",
    "                    if i != color:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t - 1) + cost[idx][i - 1])\n",
    "                    else:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t) + cost[idx][i - 1])\n",
    "            return curr\n",
    "\n",
    "        res = dfs(0, 0, target)\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(2)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            min_ = max(target-(m-i-1)-1,1)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_,target):\n",
    "                        tmp = dp[i__][t-1][:]\n",
    "                        tmp[j] = dp[i__][t][j]\n",
    "                        dp[i_][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i_][0][j] = dp[i__][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_,target):\n",
    "                    tmp = dp[i__][t-1][:]\n",
    "                    tmp[j] = dp[i__][t][j]\n",
    "                    dp[i_][t][j] = min(tmp)\n",
    "                dp[i_][0][j] = dp[i__][0][j]\n",
    "            print(dp)\n",
    "        res = min(dp[(m-1)%2][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, color, t):\n",
    "            if t < 0 or t > m - idx:\n",
    "                return float(\"inf\")\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            curr = float(\"inf\")\n",
    "            if houses[idx]:\n",
    "                if houses[idx] != color:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t - 1))\n",
    "                else:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t))\n",
    "            else:\n",
    "                for i in range(1, n + 1):\n",
    "                    if i != color:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t - 1) + cost[idx][i - 1])\n",
    "                    else:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t) + cost[idx][i - 1])\n",
    "            return curr\n",
    "\n",
    "        res = dfs(0, 0, target)\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n",
    "        '''\n",
    "        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]\n",
    "        if houses[0] == 0:\n",
    "            for i in range(n):\n",
    "                dp[0][0][i] = cost[0][i]\n",
    "        else:\n",
    "            dp[0][0][houses[0]-1] = 0\n",
    "        for i in range(1,m):\n",
    "            min_t = max(target-(m-i-1)-1,1)\n",
    "            max_t = min(target,i+2)\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    for t in range(min_t,max_t):\n",
    "                        tmp = dp[i-1][t-1][:]\n",
    "                        tmp[j] = dp[i-1][t][j]\n",
    "                        dp[i][t][j] = min(tmp) + cost[i][j]\n",
    "                    dp[i][0][j] = dp[i-1][0][j] + cost[i][j]\n",
    "            else:\n",
    "                j = houses[i]-1\n",
    "                for t in range(min_t,max_t):\n",
    "                    tmp = dp[i-1][t-1][:]\n",
    "                    tmp[j] = dp[i-1][t][j]\n",
    "                    dp[i][t][j] = min(tmp)\n",
    "                dp[i][0][j] = dp[i-1][0][j]\n",
    "        res = min(dp[-1][-1])\n",
    "        if res >= 1e6+1:\n",
    "            return -1\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, color, t):\n",
    "            if t < 0 or t > m - idx:\n",
    "                return float(\"inf\")\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            curr = float(\"inf\")\n",
    "            if houses[idx]:\n",
    "                if houses[idx] != color:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t - 1))\n",
    "                else:\n",
    "                    curr = min(curr, dfs(idx + 1, houses[idx], t))\n",
    "            else:\n",
    "                for i in range(1, n + 1):\n",
    "                    if i != color:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t - 1) + cost[idx][i - 1])\n",
    "                    else:\n",
    "                        curr = min(curr, dfs(idx + 1, i, t) + cost[idx][i - 1])\n",
    "            return curr\n",
    "\n",
    "        res = dfs(0, 0, target)\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,color,target):\n",
    "            if target==-1 or i+target>m:\n",
    "                return inf\n",
    "            if i==m:\n",
    "                return 0\n",
    "            if houses[i]!=0:\n",
    "                return dfs(i+1,houses[i],target if houses[i]==color else target-1)\n",
    "            else:\n",
    "                return min(dfs(i+1,j+1,target if color==j+1 else target-1)+cost[i][j] for j in range(n))\n",
    "        ans = dfs(0,-1,target)\n",
    "        return ans if ans!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,pre,target):\n",
    "            if i < 0:\n",
    "                return inf if target != 0 else 0\n",
    "            if target < 0 or target > i + 1:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            if houses[i] == 0:\n",
    "                for j in range(n):\n",
    "                    ans = min(ans,cost[i][j] + dfs(i - 1,j + 1,target if j + 1 == pre else target - 1))\n",
    "            else:\n",
    "                ans = dfs(i - 1,houses[i],(target if houses[i] == pre else target - 1))\n",
    "            return ans\n",
    "\n",
    "        res = dfs(m - 1,n + 1,target)\n",
    "        return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    def __init__(self):\n",
    "        self.first = float(\"inf\")\n",
    "        self.idx = -1\n",
    "        self.second = float(\"inf\")\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        houses = [c - 1 for c in houses]\n",
    "        dp = [[[float(\"inf\")]*target for _ in range(n)] for _ in range(m) ]\n",
    "        best = [[Entry() for _ in range(target)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                for k in range(target):\n",
    "                    if i == 0:\n",
    "                        if k == 0:\n",
    "                            dp[i][j][k] = 0\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "\n",
    "                        if k>0:\n",
    "                            info = best[i-1][k-1]\n",
    "                            dp[i][j][k] = min(dp[i][j][k], (info.second if j == info.idx else info.first))\n",
    "                        \n",
    "                    if houses[i] == -1 and dp[i][j][k] != float(\"inf\"):\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "                    \n",
    "                    info = best[i][k]\n",
    "                    if dp[i][j][k] < info.first:\n",
    "                        info.second = info.first\n",
    "                        info.first = dp[i][j][k]\n",
    "                        info.idx = j\n",
    "                    elif dp[i][j][k] < info.second:\n",
    "                        info.second = dp[i][j][k]\n",
    "        \n",
    "        ans = min(dp[m-1][i][target - 1] for i in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def f(i, cnt, color):   # paint house[i] color; cnt neighborhoods in [0,i]\n",
    "            if cnt <= 0 or cnt > i+1:\n",
    "                return math.inf\n",
    "            if 0 < houses[i] != color:\n",
    "                return math.inf\n",
    "            paint_cost = 0 if houses[i] else cost[i][color-1]\n",
    "            if i == 0:\n",
    "                return paint_cost\n",
    "            ans = math.inf\n",
    "            for x in range(1, n+1):\n",
    "                if x == color:\n",
    "                    ans = min(ans, f(i-1, cnt, x) + paint_cost)\n",
    "                else:\n",
    "                    ans = min(ans, f(i-1, cnt-1, x) + paint_cost)\n",
    "            return ans\n",
    "\n",
    "        ans = min(f(m-1, target, i) for i in range(1, n+1))\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Entry:\n",
    "    def __init__(self):\n",
    "        self.first = float(\"inf\")\n",
    "        self.idx = -1\n",
    "        self.second = float(\"inf\")\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        houses = [c - 1 for c in houses]\n",
    "        dp = [[[float(\"inf\")]*target for _ in range(n)] for _ in range(m) ]\n",
    "        best = [[Entry() for _ in range(target)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:\n",
    "                    continue\n",
    "                for k in range(target):\n",
    "                    if i == 0:\n",
    "                        if k == 0:\n",
    "                            dp[i][j][k] = 0\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "\n",
    "                        if k>0:\n",
    "                            info = best[i-1][k-1]\n",
    "                            dp[i][j][k] = min(dp[i][j][k], (info.second if j == info.idx else info.first))\n",
    "                        \n",
    "                    if houses[i] == -1 and dp[i][j][k] != float(\"inf\"):\n",
    "                        dp[i][j][k] += cost[i][j]\n",
    "                    \n",
    "                    info = best[i][k]\n",
    "                    if dp[i][j][k] < info.first:\n",
    "                        info.second = info.first\n",
    "                        info.first = dp[i][j][k]\n",
    "                        info.idx = j\n",
    "                    elif dp[i][j][k] < info.second:\n",
    "                        info.second = dp[i][j][k]\n",
    "        \n",
    "        ans = min(dp[m-1][i][target - 1] for i in range(n))\n",
    "        return -1 if ans == float(\"inf\") else ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def f(i, cnt, color):\n",
    "            if cnt <= 0 or cnt > i+1:\n",
    "                return math.inf\n",
    "            if 0 < houses[i] != color:\n",
    "                return math.inf\n",
    "            if i == 0:\n",
    "                if houses[i] == 0:\n",
    "                    return cost[i][color-1]\n",
    "                else:\n",
    "                    return 0\n",
    "            ans = math.inf\n",
    "            if houses[i] == 0:\n",
    "                for x in range(1, n+1):\n",
    "                    if x == color:\n",
    "                        ans = min(ans, f(i-1, cnt, x) + cost[i][color-1])\n",
    "                    else:\n",
    "                        ans = min(ans, f(i-1, cnt-1, x) + cost[i][color-1])\n",
    "            else:\n",
    "                for x in range(1, n+1):\n",
    "                    if x == color:\n",
    "                        ans = min(ans, f(i-1, cnt, x))\n",
    "                    else:\n",
    "                        ans = min(ans, f(i-1, cnt-1, x))\n",
    "            return ans\n",
    "\n",
    "        ans = min(f(m-1, target, i) for i in range(1, n+1))\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        def getMinDiffC(i, c, t):\n",
    "            curMin = inf\n",
    "            for cc in range(1, n+1):\n",
    "                if cc != c:\n",
    "                    curMin = min(dp(i-1, cc, t-1), curMin)\n",
    "                    # print(i-1, cc, t-1, dp(i-1, cc, t-1))\n",
    "            return curMin\n",
    "        @cache\n",
    "        def dp(i, c, t):\n",
    "            # print(i, c, t)\n",
    "            if i < 0: return 0\n",
    "            if i+1 < t: return inf\n",
    "            if houses[i] != 0 and houses[i] != c: return inf\n",
    "            minCostSameT = dp(i-1, c, t)\n",
    "            paintCost = 0\n",
    "            if houses[i] == 0:\n",
    "                paintCost = cost[i][c-1]\n",
    "            sameTCost = minCostSameT+paintCost\n",
    "            if t == 1: \n",
    "                return sameTCost\n",
    "            minCostDiffT = getMinDiffC(i, c, t)\n",
    "            diffTCost = minCostDiffT+paintCost\n",
    "            return min(diffTCost, sameTCost)\n",
    "        ret = inf\n",
    "        for cc in range(1, n+1):\n",
    "            ret = min(ret, dp(m-1, cc, target))\n",
    "            # print(dp(m-1, cc, target))\n",
    "        return ret if ret != inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        houses = [c - 1 for c in houses]\n",
    "        dp = [[[float('inf') for _ in range(target)] for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if houses[i] != -1 and houses[i] != j:  #不要重复染色，或者染错色\n",
    "                    continue\n",
    "                for t in range(target):\n",
    "                    for j0 in range(n):\n",
    "                        if j0 == j:     #正是当前的颜色\n",
    "                            if i == 0:\n",
    "                                if t == 0:\n",
    "                                    dp[i][j][t] = 0\n",
    "                            else:\n",
    "                                dp[i][j][t] = min(dp[i][j][t], dp[i-1][j][t])\n",
    "                        \n",
    "                        elif i > 0 and t > 0:   #不是当前的颜色\n",
    "                            dp[i][j][t] = min(dp[i][j][t], dp[i-1][j0][t-1])\n",
    "                    if dp[i][j][t] != float('inf') and houses[i] == -1: #前面都是当已经染色了算的\n",
    "                        dp[i][j][t] += cost[i][j]\n",
    "\n",
    "        res = min(dp[m - 1][j][target - 1] for j in range(n))\n",
    "        return res if res != float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[float('inf') for _ in range(target)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(target):\n",
    "                    if i <= target - 1 and k > i:\n",
    "                        pass\n",
    "                    else:\n",
    "                        dp[i][j][k] = cost[i][j]\n",
    "                        if houses[i] != 0:\n",
    "                            if j != houses[i] - 1:\n",
    "                                dp[i][j][k] = float('inf')\n",
    "                            else:\n",
    "                                dp[i][j][k] = 0\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in range(target):\n",
    "                    if k == 0:\n",
    "                        dp[i][j][k] += dp[i - 1][j][k]\n",
    "                    else:\n",
    "                        dp[i][j][k] += min(dp[i - 1][j][k],\n",
    "                                        min(dp[i - 1][p][k - 1]\n",
    "                                            for p in range(n) if p != j))\n",
    "                    \n",
    "\n",
    "\n",
    "        ans = min(dp[-1][p][target - 1] for p in range(n))\n",
    "        return(ans if ans!=float('inf') else -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[float('inf') for _ in range(target)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(target):\n",
    "                    if target - 1 >= i and k > i:\n",
    "                        break\n",
    "                    else:\n",
    "                        dp[i][j][k] = cost[i][j]\n",
    "\n",
    "        for i in range(m):\n",
    "            if houses[i] != 0:\n",
    "                for j in range(n):\n",
    "                    for k in range(target):\n",
    "                        if i <= target - 1 and k > i:\n",
    "                            pass\n",
    "                        elif j != houses[i] - 1:\n",
    "                            dp[i][j][k] = float('inf')\n",
    "                        else:\n",
    "                            dp[i][j][k] = 0\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in range(target):\n",
    "                    if dp[i][j][k] != -1:\n",
    "                        if k == 0:\n",
    "                            dp[i][j][k] += dp[i - 1][j][k]\n",
    "                        else:\n",
    "                            dp[i][j][k] += min(dp[i - 1][j][k],\n",
    "                                            min(dp[i - 1][p][k - 1]\n",
    "                                                for p in range(n) if p != j))\n",
    "                            # print(i, j, k, dp[i][j][k])\n",
    "\n",
    "\n",
    "        ans = min(dp[-1][p][target - 1] for p in range(n))\n",
    "        return(ans if ans!=float('inf') else -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[[float('inf')]*(n) for j in range(target)] for _ in range(m)]\n",
    "        dp2 = [[[float('inf')]*(n) for j in range(target)] for _ in range(m)]\n",
    "\n",
    "        def otherMin(lst):\n",
    "            lmin = [float('inf')]\n",
    "            for i in range(len(lst)-1):\n",
    "                lmin.append(min(lmin[-1], lst[i]))\n",
    "            \n",
    "            rmin = [float('inf')]\n",
    "            for i in range(len(lst)-1,0,-1):\n",
    "                rmin.append(min(rmin[-1], lst[i]))\n",
    "            rmin = rmin[::-1]\n",
    "\n",
    "            omin = []\n",
    "            for i in range(len(lst)):\n",
    "                omin.append(min(lmin[i], rmin[i]))\n",
    "            \n",
    "            return omin\n",
    "\n",
    "        if houses[0] == 0:\n",
    "            for c in range(n):\n",
    "                dp[0][0][c] = cost[0][c]\n",
    "            dp2[0][0] = otherMin(dp[0][0])\n",
    "        else:\n",
    "            c = houses[0]-1\n",
    "            dp[0][0][c] = 0\n",
    "            for c in range(n):\n",
    "                if c != houses[0]-1:\n",
    "                    dp2[0][0][c] = 0\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for t in range(target):\n",
    "                if houses[i] == 0:\n",
    "                    for c in range(n):\n",
    "                        dp[i][t][c] = cost[i][c] + dp[i-1][t][c]\n",
    "                        if t > 0:\n",
    "                            dp[i][t][c] = min(dp[i][t][c], dp2[i-1][t-1][c]+cost[i][c])\n",
    "                else:\n",
    "                    c = houses[i]-1\n",
    "                    dp[i][t][c] = dp[i-1][t][c]\n",
    "                    if t > 0:\n",
    "                        dp[i][t][c] = min(dp[i][t][c], dp2[i-1][t-1][c])\n",
    "                \n",
    "                dp2[i][t] = otherMin(dp[i][t])\n",
    "        \n",
    "        if min(dp[m-1][target-1]) == float('inf'):\n",
    "            return -1\n",
    "        \n",
    "        return min(dp[m-1][target-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 定义函数dfs(idx, cur, pre): 返回从下标idx开始，在已经有cur个街区且前一个房屋颜色为pre时的最小花费，若无法使得总街区数量达到target则返回inf\n",
    "        @cache\n",
    "        def dfs(idx, cur, pre):\n",
    "            if idx == m:\n",
    "                return 0 if cur == target else inf\n",
    "            # 当cur等于target但后面仍有房屋时，只能将后续房屋涂成pre颜色\n",
    "            # 使houses[idx - 1:]中元素都是同一个值，即是同一个街区\n",
    "            if cur == target:\n",
    "                lis = houses[idx:]\n",
    "                # 验证后面的房屋是否满足涂色条件\n",
    "                set_ = set(lis)\n",
    "                if 0 in set_: set_.remove(0)\n",
    "                if len(set_) > 1 or (set_ and set_.pop() != pre): return inf\n",
    "                # 计算后面未涂色房屋涂色的总价格。根据实测，没有测试用例能执行到此行代码(之前少打了个return，但依然可以AC)\n",
    "                return sum(cost[i][pre - 1] for i, h in enumerate(lis, start = idx) if h == 0)\n",
    "            c = houses[idx]\n",
    "            # 当前房屋已有颜色，跳过\n",
    "            if c: return dfs(idx + 1, cur + (c != pre), c)\n",
    "            # 枚举涂色方案，从所有方案中取最小花费即可\n",
    "            return min(cost[idx][i - 1] + dfs(idx + 1, cur + (i != pre), i) for i in range(1, n + 1))\n",
    "        \n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 定义函数dfs(idx, cur, pre): 返回从下标idx开始，在已经有cur个街区且前一个房屋颜色为pre时的最小花费，若无法使得总街区数量达到target则返回inf\n",
    "        @cache\n",
    "        def dfs(idx, cur, pre):\n",
    "            if idx == m:\n",
    "                return 0 if cur == target else inf\n",
    "            # 当cur等于target但后面仍有房屋时，只能将后续房屋涂成pre颜色\n",
    "            # 使houses[idx - 1:]中元素都是同一个值，即是同一个街区\n",
    "            if cur == target:\n",
    "                lis = houses[idx:]\n",
    "                # 验证后面的房屋是否满足涂色条件\n",
    "                set_ = set(lis)\n",
    "                if 0 in set_: set_.remove(0)\n",
    "                if len(set_) > 1 or (set_ and set_.pop() != pre): return inf\n",
    "                # 计算后面未涂色房屋涂色的总价格。根据实测，没有测试用例能执行到此行代码(之前少打了个return，但依然可以AC)\n",
    "                return sum(cost[i][pre - 1] for i, h in enumerate(lis, start = idx) if h == 0)\n",
    "            c = houses[idx]\n",
    "            # 当前房屋已有颜色，跳过\n",
    "            if c: return dfs(idx + 1, cur + (c != pre), c)\n",
    "            # 枚举涂色方案，从所有方案中取最小花费即可\n",
    "            return min(cost[idx][i - 1] + dfs(idx + 1, cur + (i != pre), i) for i in range(1, n + 1))\n",
    "        \n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        mcost = dict()\n",
    "\n",
    "        pre_set = set()\n",
    "        for i, hcolor in enumerate(houses):\n",
    "            cur_set = set()\n",
    "            if i == 0:\n",
    "                if hcolor == 0:\n",
    "                    for j in range(1, n + 1):\n",
    "                        mcost[(i, j, 1)] = cost[i][j - 1]\n",
    "                        cur_set.add((j, 1))\n",
    "                else:\n",
    "                    mcost[(i, hcolor, 1)] = 0\n",
    "                    cur_set.add((hcolor, 1))\n",
    "            else:\n",
    "                if hcolor == 0:\n",
    "                    for j in range(1, n + 1):\n",
    "                        for pre_color, pre_cnt in pre_set:\n",
    "                            cnt = pre_cnt + 1 if pre_color != j else pre_cnt\n",
    "                            key = (i, j, cnt)\n",
    "                            ccost = mcost[(i - 1, pre_color, pre_cnt)] + cost[i][j - 1]\n",
    "                            if key not in mcost or mcost[key] > ccost:\n",
    "                                mcost[key] = ccost\n",
    "                                cur_set.add((j, cnt))\n",
    "                else:\n",
    "                    for pre_color, pre_cnt in pre_set:\n",
    "                        cnt = pre_cnt + 1 if pre_color != hcolor else pre_cnt\n",
    "                        key = (i, hcolor, cnt)\n",
    "                        ccost = mcost[(i - 1, pre_color, pre_cnt)]\n",
    "                        if key not in mcost or mcost[key] > ccost:\n",
    "                            mcost[key] = ccost\n",
    "                            cur_set.add((hcolor, cnt))\n",
    "\n",
    "            pre_set = cur_set\n",
    "\n",
    "        res = -1\n",
    "        for j in range(1, n + 1):\n",
    "            if (m - 1, j, target) in mcost:\n",
    "                if res == -1 or (res >= 0 and mcost[(m - 1, j, target)] < res):\n",
    "                    res = mcost[(m - 1, j, target)]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        dp = [[np.inf]*n for _ in range(m)]\n",
    "        if houses[0]:\n",
    "            dp[0][houses[0]-1] = 0\n",
    "        else:\n",
    "            dp[0][:] = cost[0]\n",
    "\n",
    "        for j in range(1, m):\n",
    "            if houses[j]:\n",
    "                dp[j][houses[j]-1] = dp[j-1][houses[j]-1]\n",
    "            else:\n",
    "                for k in range(n):\n",
    "                    dp[j][k] = cost[j][k] + dp[j-1][k]\n",
    "        \n",
    "        for i in range(1, target):\n",
    "            dp1 = [[np.inf]*n for _ in range(m)]\n",
    "            for j in range(i, m):\n",
    "                if houses[j]:\n",
    "                    dp1[j][houses[j]-1] = min(np.inf, np.inf if j == i else dp1[j-1][houses[j]-1], *[dp[j-1][k] for k in range(n) if not k+1 == houses[j]])\n",
    "                else:\n",
    "                    for k in range(n):\n",
    "                        dp1[j][k] = cost[j][k] + min(np.inf, np.inf if j == i else dp1[j-1][k], *[dp[j-1][k1] for k1 in range(n) if not k1 == k])\n",
    "            dp = dp1\n",
    "\n",
    "        m = min(np.inf, *dp[-1])\n",
    "        if m is np.inf:\n",
    "            return -1\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(prev, u, t):\n",
    "            if t < 0:\n",
    "                return inf\n",
    "            if u == m:\n",
    "                return 0 if t == 0 else inf            \n",
    "            if houses[u] != 0:\n",
    "                return dfs(houses[u], u + 1, t - (houses[u] != prev))\n",
    "            else:\n",
    "                return min(dfs(i, u + 1, t - (i != prev)) + cost[u][i-1] for i in range(1, n+1))\n",
    "        ans = dfs(0, 0, target)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            if i == m:\n",
    "                return 0 if j == 0 else inf\n",
    "            if j < 0:\n",
    "                return inf\n",
    "            if houses[i] != 0:\n",
    "                return dfs(i + 1, j - (houses[i] != c), houses[i])\n",
    "            return min(dfs(i + 1, j - (t + 1 != c), t + 1) + cost[i][t] for t in range(n))\n",
    "        ans = dfs(0, target, -1)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            if i == m:\n",
    "                return 0 if j == 0 else inf\n",
    "            if houses[i] != 0:\n",
    "                return dfs(i + 1, j - (houses[i] != c), houses[i])\n",
    "            return min(dfs(i + 1, j - (t + 1 != c), t + 1) + cost[i][t] for t in range(n))\n",
    "        ans = dfs(0, target, -1)\n",
    "        return ans if ans != inf else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
